【本题解采用动态规划备忘录方法,由于时间复杂度过大,通过74/76测试用例。测试用例在本机环境下可通过。】
给你一个整数数组 nums ,判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ,使得 nums[i] < nums[j] < nums[k] ,返回 true ;否则,返回 false 。
示例 1:
输入:nums = [1,2,3,4,5]
输出:true
解释:任何 i < j < k 的三元组都满足题意
示例 2:
输入:nums = [5,4,3,2,1]
输出:false
解释:不存在满足题意的三元组
示例 3:
输入:nums = [2,1,5,0,4,6]
输出:true
解释:三元组 (3, 4, 5) 满足题意,因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
提示:
1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1
进阶:你能实现时间复杂度为 O(n) ,空间复杂度为 O(1) 的解决方案吗?
#include#include using namespace std; bool increasingTriplet(vector &nums, vector > &memtable) { int length = nums.size(); vector > processTable(length, vector (length, 0)); vector > curSubseq(length, vector (length, 0)); for (int k = 0; k < length; k++) { for (int i = 0; i < length - k; i++) { int j = i + k; if (i == j) { processTable[i][i] = 1; curSubseq[i][i] = nums[i]; } else { if (nums[j] > curSubseq[i][j - 1]) { processTable[i][j] = processTable[i][j - 1] + 1; curSubseq[i][j] = nums[j]; } else { processTable[i][j] = processTable[i][j - 1]; if (nums[j] > nums[i]) { curSubseq[i][j] = nums[j]; } else { curSubseq[i][j] = curSubseq[i][j - 1]; } } } if (processTable[i][j] == 3) { memtable = processTable; return true; } } } memtable = processTable; return false; } int main() { vector nums = {0, 4, 1, 3}; vector > memtable{nums.size(), vector (nums.size(), 0)}; printf("%dn", increasingTriplet(nums, memtable)); for (int i = 0; i < nums.size(); i++) { for (int j = 0; j < nums.size(); j++) { printf("%d ", memtable[i][j]); } printf("n"); } return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)