作者：东儿2502858537 | 来源：互联网 | 2024-12-23 15:00
本题探讨如何通过单调栈的方法，找到一个数组中最短的需要排序的连续子数组。通过正向和反向遍历，分别使用单调递增栈和单调递减栈来确定边界索引，从而定位出最小的无序子数组。
题目：
给定一个整数数组 nums，请找出其中最短的连续子数组，使其排序后整个数组变为有序。返回该子数组的长度。
解答：
为了高效地解决这个问题，我们可以利用单调栈的思想。具体步骤如下：
- 初始化两个变量
l 和 r 分别表示最小子数组的左边界和右边界。
- 正向遍历数组，使用单调递增栈来查找所有违反递增顺序的元素，并记录下这些元素中最早出现的位置作为左边界
l。
- 反向遍历数组，使用单调递减栈来查找所有违反递减顺序的元素，并记录下这些元素中最晚出现的位置作为右边界
r。
- 最终，如果
r > l，则返回 r - l + 1；否则返回 0，表示整个数组已经是有序的。
1 class Solution {
2 public:
3 int findUnsortedSubarray(vector& nums) {
4 stack st;
5 int l = nums.size() - 1;
6 int r = 0;
7 for (int i = 0; i 8 while (!st.empty() && nums[st.top()] > nums[i]) {
9 l = min(l, st.top());
10 st.pop();
11 }
12 st.push(i);
13 }
14
15 st = stack();
16 for (int i = nums.size() - 1; i >= 0; i--) {
17 while (!st.empty() && nums[st.top()] 18 r = max(r, st.top());
19 st.pop();
20 }
21 st.push(i);
22 }
23 return (r > l) ? r - l + 1 : 0;
24 }
25 };
京公网安备 11010802041100号