网站建设海淀,wordpress首页轮播图片尺寸,门户网站代码,joomla 网站建设教程文章目录1. 题目2. 解题2.1 排序2.2 4次遍历2.3 单调栈1. 题目
给定一个整数数组#xff0c;你需要寻找一个连续的子数组#xff0c;如果对这个子数组进行升序排序#xff0c;那么整个数组都会变为升序排序。
你找到的子数组应是最短的#xff0c;请输出它的长度。
示例…
文章目录1. 题目2. 解题2.1 排序2.2 4次遍历2.3 单调栈1. 题目
给定一个整数数组你需要寻找一个连续的子数组如果对这个子数组进行升序排序那么整个数组都会变为升序排序。
你找到的子数组应是最短的请输出它的长度。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序那么整个表都会变为升序排序。
说明 :
输入的数组长度范围在 [1, 10,000]。
输入的数组可能包含重复元素 所以升序的意思是。来源力扣LeetCode 链接https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
从前后分别遍历碰到第一个拐点开始找后面的最小值和前面的最大值将最大最小值插入到原数组中的位置即形成了答案的最小区间
2.1 排序
排序后不相等的最大区间就是需要排序的
class Solution {
public:int findUnsortedSubarray(vectorint nums) {vectorint sorted(nums);sort(sorted.begin(), sorted.end());int i nums.size()-1, j 0;for(int k 0; k nums.size(); k){if(nums[k] ! sorted[k]){i min(i,k);j max(j,k);}}if(j i)return j-i1;return 0;}
};2.2 4次遍历
4次遍历
class Solution {
public:int findUnsortedSubarray(vectorint nums) {if(nums.size() 1)return 0;int i, MIN INT_MAX, MAX INT_MIN;bool flag false;for(i 1; i nums.size(); i){if(nums[i-1] nums[i])flag true;if(flag)MIN min(MIN,nums[i]);//找拐点后面的最小值}flag false;for(i nums.size()-2; i 0; --i){if(nums[i] nums[i1])flag true;if(flag)MAX max(MAX,nums[i]);//找拐点前面的最大值}int l,r;for(l 0; l nums.size(); l)if(MIN nums[l])//最小值插入位置break;for(r nums.size()-1; r 0; --r)if(MAX nums[r])//最大值插入的位置break;if(r l)return r-l1;return 0;}
};2.3 单调栈
class Solution {
public:int findUnsortedSubarray(vectorint nums) {int i, l nums.size()-1, r 0, idx;stackint stk;//存放下标for(i 0; i nums.size(); i){if(stk.empty() || nums[i] nums[stk.top()])stk.push(i);else{while(!stk.empty() nums[stk.top()] nums[i]){idx stk.top();stk.pop();}l min(l,idx);//每一个拐点后的数能顶到的最左端(有多小)}}while(!stk.empty())stk.pop();//清空for(i nums.size()-1; i 0; --i){if(stk.empty() || nums[i] nums[stk.top()])stk.push(i);else{while(!stk.empty() nums[stk.top()] nums[i]){idx stk.top();stk.pop();}r max(r,idx);//每一个拐点后的数能顶到的最右端有多大}}if(rl)return r-l1;return 0;}
};
