目錄

• 42. 接雨水
• • 思路分析
• 901. 股票價格跨度
• • 思路
• 581. 最短無序連續子數組
• • 思路一：排序+雙指針
  • 思路二：單調棧
  • 思路三：雙指針(最省時)

42. 接雨水

42. 接雨水
給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。

輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
解釋：上面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍色部分表示雨水）。

示例 2：

輸入：height = [4,2,0,3,2,5] 輸出：9

提示：

n == height.length
0 <= n <= 3 * 10^4
0 <= height[i] <= 10^5

思路分析

由于這一題方法比較多，就專門寫了一個：
https://blog.csdn.net/qq_42604176/article/details/111053090

901. 股票價格跨度

編寫一個 StockSpanner 類，它收集某些股票的每日報價，并返回該股票當日價格的跨度。

今天股票價格的跨度被定義為股票價格小于或等于今天價格的最大連續日數（從今天開始往回數，包括今天）。

例如，如果未來7天股票的價格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度將是 [1, 1, 1, 2, 1, 4, 6]。
示例：

輸入：[“StockSpanner”,“next”,“next”,“next”,“next”,“next”,“next”,“next”], [[],[100],[80],[60],[70],[60],[75],[85]]
輸出：[null,1,1,1,2,1,4,6]
解釋：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被調用并返回 1，
S.next(80) 被調用并返回 1，
S.next(60) 被調用并返回 1，
S.next(70) 被調用并返回 2，
S.next(60) 被調用并返回 1，
S.next(75) 被調用并返回 4，
S.next(85) 被調用并返回 6。

注意 (例如) S.next(75) 返回 4，因為截至今天的最后 4 個價格
(包括今天的價格 75) 小于或等于今天的價格。

思路

仍然是單調棧的思路，構造一個單調遞減棧。
1、如果當前棧為空，輸入元素在原數組中的下標壓入棧中。
獲取該元素左邊極大值的坐標，此時棧為空，說明左邊沒有比該元素還小的元素，所以左邊極大值坐標就是不存在，填-1(不能填0)
然后返回長度就是當前元素在原數組中下標 - 左極大值坐標。
可以想象一下，如果左邊極大值不存在的時候，我們填入0，而當前輸入元素正好是第0個元素，那么顯然結果就是0 - 0 = 0 ，不符合答案1。
2、如果當前棧不為空，并且棧頂元素小于等于輸入元素。
此時根據題目要求：小于或等于今天價格的最大連續日數，我們必須要找到大于今日價格才能停止尋找，所以仍然需要回撤操作。
直到棧為空或者棧頂元素大于今日價格，才停止回撤。
如果棧為空，說明左邊沒有比該元素還小的元素，所以左邊極大值坐標就是不存在，填-1(不能填0)
如果棧不為空，左極大值坐標就是當前棧頂元素坐標。
最后將今日 - 左極大值日期，就是結果

和之前系列中有的操作還是相似的，例如棧中記錄的不是元素，而是該元素在原數組中的下標。
對于棧頂元素與當前元素的比較，仍然是需要結合題意，列出三種可能：當前元素 < 、 == 、 > st.back()，找到符合題意的出棧標準

class StockSpanner {
private:vector<int> input;vector<int> st;
public:StockSpanner() {}int next(int price) {//輸入一個price,input數組又多了一個元素input.emplace_back(price);//該元素為input數組末尾int now_index = input.size() - 1;//如果此時棧為空，說明它左邊沒有值while(!st.empty() && input[st.back()] <= price){st.pop_back();}//獲取該元素左邊極大值的下標，如果棧為空的話，說明沒有，那么left_max就是-1；如果不為空，返回棧頂int left_max_index;if(st.empty()) left_max_index = -1;else left_max_index = st.back();//當前元素入棧st.push_back(now_index);return (now_index - left_max_index);}
};/*** Your StockSpanner object will be instantiated and called as such:* StockSpanner* obj = new StockSpanner();* int param_1 = obj->next(price);*/

581. 最短無序連續子數組

給定一個整數數組，你需要尋找一個連續的子數組，如果對這個子數組進行升序排序，那么整個數組都會變為升序排序。
你找到的子數組應是最短的，請輸出它的長度。
示例 1:

輸入: [2, 6, 4, 8, 10, 9, 15]
輸出: 5
解釋: 你只需要對 [6, 4, 8, 10, 9] 進行升序排序，那么整個表都會變為升序排序。

說明 :

輸入的數組長度范圍在 [1, 10,000]。
輸入的數組可能包含重復元素 ，所以升序的意思是<=。

思路一：排序+雙指針

先排序，然后將排序后的數組與原數組進行比對(從左到右、從右到左)。
找到左右邊界，然后最后的結果就是左右邊界差值+1.
當然還要考慮特殊情況：原數組本身是單調遞增或遞減的，這樣我們就不能對左右邊界進行更新。
但是我們知道單調的結果：無非是0(單調遞增不需要重新排序)，和nums.size()（單調遞減需要將整個數組都排序）.

class Solution {
public:int findUnsortedSubarray(vector<int>& nums) {vector<int> _new = nums;sort(_new.begin(),_new.end());int left_index = -1;int right_index = -1;//雙指針left、right，從兩邊向中間遍歷for(int left = 0; left < nums.size(); left++){if(nums[left] != _new[left]){left_index = left;break;}}for(int right = nums.size() - 1; right >= 0; right--){if(nums[right] != _new[right]){right_index = right;break;}}//如果是單調遞增,不需要修改，返回0if(left_index == -1) return 0;//如果是單調遞減，返回整個長度if(right_index == -1) return nums.size();return (right_index - left_index + 1);}
};

思路二：單調棧

背后的思想仍然是選擇排序，我們需要找到無序子數組中最小元素和最大元素分別對應的正確位置。
來求我們需要的無序子數組的邊界。
使用棧，從頭遍歷nums數組：
1、如果遇到的數組大小一直升序的，我們就不斷把對應的下標壓入棧中，目的：這些元素目前都是出于正確的位置上
2、一旦當前數字比棧頂元素小，那么我們知道nums[j]一定不在正確的位子上
3、既然這樣，我們就需要找到nums[j]的正確位置：
不斷將棧頂元素彈出，知道棧頂元素比nums[j]，假設此刻棧頂元素對應的下標是k，那么我們知道nums[j]的正確下標應該是k+1
4、重復上述過程，直到遍歷完整個數組，這樣我們可以找到最小的k，它也是無序子數組的左邊界。
5、類似的，我們逆序遍歷一遍nums數組來找到無序子數組的右邊界。這一次我們將降序的元素壓入棧中。
6、如果遇到一個升序的元素，不斷將棧頂元素彈出，直到找到一個更大的元素，以此找到無序子數組的右邊界

class Solution {
public:int findUnsortedSubarray(vector<int>& nums) {vector<int> st;int left = nums.size() - 1;int right = 0;for(int i = 0; i < nums.size(); i++){while(!st.empty() && nums[i] < nums[st.back()]){left = min(left,st.back()); st.pop_back();}st.emplace_back(i);}st.clear();for(int i = nums.size() - 1; i >= 0; i--){while(!st.empty() && nums[i] > nums[st.back()]){right = max(right,st.back()); st.pop_back();}st.emplace_back(i);}return right - left > 0 ? right - left + 1 : 0;}
};

思路三：雙指針(最省時)

這一題的雙指針解法和接雨水的雙指針思想有一定相似性：
leetcode 42. 接雨水 思考分析(暴力、動態規劃、雙指針、單調棧)
我們要做的是，找到無序數組的上下界。
運用到本題，就是下面兩個想法:
https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/shi-jian-chao-guo-100de-javajie-fa-by-zackqf/
https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/jian-dan-zhi-guan-de-shuang-zhi-zhen-fa-by-sillywo/
無序子數組中最小元素的正確位置可以決定左邊界，最大元素的正確位置可以決定右邊界。
尋找右邊界：
從左往右遍歷，用max記錄遍歷過的最大值，如果max大于當前nums[i]，說明nums[i]的位子不正確，屬于需要排序的數組，所以右邊界就需要更新為i
如果nums[i]大于max更新max，繼續往右檢查，是否有元素比更新之后的max要小；最終可以找到需要排序的數組的右邊界，右邊界之后的元素都大于max。
尋找左邊界：
從右向左遍歷，yongmin記錄當前遍歷過的最小值，如果min小于當前nums[i]，說明nums[i]的位子不正確，屬于需要排序的數組，所以更新左邊界
如果nums[i]小于min更新min，繼續往左檢查，是否有元素比更新之后的min要大，最終可以找到需要排序的數組的左邊界，左邊界之前的元素都小于min

class Solution {
public:int findUnsortedSubarray(vector<int>& nums) {//特判int n = nums.size();if (n <= 1) {return 0;}//從右到左找下界，從左到右找上界int left = n - 2, right = 1; int curMin = nums[n - 1], curMax = nums[0];int up = 0, down = 1;//升序時移動 curMin 和 curMax//逆序時移動 down 和 up//不論順序如何，雙指針 left 和 rigt 一直保持移動while (left >=0 && right < n) {if (nums[left] > curMin){down = left;}else {curMin = nums[left];}left--;if (nums[right] < curMax) {up = right;}else {curMax = nums[right];}right++;}return up - down + 1;}
};

單調棧暫時就刷到這兒，接下來繼續刷雙指針的題目吧。