leetcode 581. Shortest Unsorted Continuous Subarray | 581. 最短无序连续子数组（单调栈）

水深无声 2022-08-28 08:53 138阅读 0赞

## 题目 ##

[https://leetcode.com/problems/shortest-unsorted-continuous-subarray/][https_leetcode.com_problems_shortest-unsorted-continuous-subarray]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

乍一看，没思路，直奔 Related Topics，发现是个单调栈。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

class Solution { 
        public int findUnsortedSubarray(int[] nums) { 
            int N = nums.length;
    
            int[] leftMax = new int[N];
            leftMax[0] = nums[0];
            for (int i = 1; i < N; i++) { 
                leftMax[i] = Math.max(leftMax[i - 1], nums[i]);
            }
    
            int[] rightMin = new int[N];
            rightMin[N - 1] = nums[N - 1];
            for (int i = N - 2; i >= 0; i--) { 
                rightMin[i] = Math.min(rightMin[i + 1], nums[i]);
            }
    
            // 找到满足 leftMax > rightMin 的第一个和最后一个位置
            int L = -1;
            int R = -1;
            for (int i = 0; i < N; i++) { 
                if (leftMax[i] > rightMin[i]) { 
                    L = i;
                    break;
                }
            }
            for (int i = N - 1; i >= 0; i--) { 
                if (leftMax[i] > rightMin[i]) { 
                    R = i;
                    break;
                }
            }
            return L == -1 ? 0 : R - L + 1;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]

[https_leetcode.com_problems_shortest-unsorted-continuous-subarray]: https://leetcode.com/problems/shortest-unsorted-continuous-subarray/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/6a6a9adc26a442f8a301ac0bcddf320c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/0153ac3a049e494a9f6b2ed685f4685e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/0e77eef117464f30bae3dd2145660262.png