/**
Given an integer array nums, you need to find one continuous subarray that if
you only sort this subarray in ascending order, then the whole array will be
sorted in ascending order.
Return the shortest such subarray and output its length.
Example 1:
Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the
whole array sorted in ascending order.
Example 2:
Input: nums = [1,2,3,4]
Output: 0
Example 3:
Input: nums = [1]
Output: 0
Constraints:
1 <= nums.length <= 10⁴
-10⁵ <= nums[i] <= 10⁵
Follow up: Can you solve it in O(n) time complexity? Related Topics栈 | 贪心 | 数组 |
双指针 | 排序 | 单调栈
👍 952, 👎 0
*/
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int findUnsortedSubarray(int[] nums) {
if (nums == null || nums.length <= 1) {
return 0;
}
Stack<Integer> ascStack = new Stack<>();
Stack<Integer> descStack = new Stack<>();
boolean ascIn = true;
boolean descIn = true;
for (int i = 0; i < nums.length; i++) {
if (ascIn && (ascStack.isEmpty() || nums[i] >= ascStack.peek())) {
ascStack.push(nums[i]);
} else {
ascIn = false;
while (!ascStack.isEmpty() && nums[i] < ascStack.peek()) {
ascStack.pop();
}
}
if (descIn && (descStack.isEmpty() || nums[nums.length - 1 - i] <= descStack.peek())) {
descStack.push(nums[nums.length - 1 - i]);
} else {
descIn = false;
while (!descStack.isEmpty() && nums[nums.length - 1 - i] > descStack.peek()) {
descStack.pop();
}
}
}
if (ascStack.size() == nums.length) {
return 0;
} else {
return nums.length - ascStack.size() - descStack.size();
}
}
}
//leetcode submit region end(Prohibit modification and deletion)
