目錄

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

42. 接雨水

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

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

示例 2：

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

提示：

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

思路分析

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

901. 股票價(jià)格跨度

編寫一個(gè) StockSpanner 類，它收集某些股票的每日?qǐng)?bào)價(jià)，并返回該股票當(dāng)日價(jià)格的跨度。

今天股票價(jià)格的跨度被定義為股票價(jià)格小于或等于今天價(jià)格的最大連續(xù)日數(shù)（從今天開始往回?cái)?shù)，包括今天）。

例如，如果未來(lái)7天股票的價(jià)格是 [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) 被調(diào)用并返回 1，
S.next(80) 被調(diào)用并返回 1，
S.next(60) 被調(diào)用并返回 1，
S.next(70) 被調(diào)用并返回 2，
S.next(60) 被調(diào)用并返回 1，
S.next(75) 被調(diào)用并返回 4，
S.next(85) 被調(diào)用并返回 6。

注意 (例如) S.next(75) 返回 4，因?yàn)榻刂两裉斓淖詈?4 個(gè)價(jià)格
(包括今天的價(jià)格 75) 小于或等于今天的價(jià)格。

思路

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

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

class StockSpanner { private:vector<int> input;vector<int> st; public:StockSpanner() {}int next(int price) {//輸入一個(gè)price,input數(shù)組又多了一個(gè)元素input.emplace_back(price);//該元素為input數(shù)組末尾int now_index = input.size() - 1;//如果此時(shí)棧為空，說(shuō)明它左邊沒(méi)有值while(!st.empty() && input[st.back()] <= price){st.pop_back();}//獲取該元素左邊極大值的下標(biāo)，如果棧為空的話，說(shuō)明沒(méi)有，那么left_max就是-1；如果不為空，返回棧頂int left_max_index;if(st.empty()) left_max_index = -1;else left_max_index = st.back();//當(dāng)前元素入棧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. 最短無(wú)序連續(xù)子數(shù)組

給定一個(gè)整數(shù)數(shù)組，你需要尋找一個(gè)連續(xù)的子數(shù)組，如果對(duì)這個(gè)子數(shù)組進(jìn)行升序排序，那么整個(gè)數(shù)組都會(huì)變?yōu)樯蚺判颉?br /> 你找到的子數(shù)組應(yīng)是最短的，請(qǐng)輸出它的長(zhǎng)度。
示例 1:

輸入: [2, 6, 4, 8, 10, 9, 15]
輸出: 5
解釋: 你只需要對(duì) [6, 4, 8, 10, 9] 進(jìn)行升序排序，那么整個(gè)表都會(huì)變?yōu)樯蚺判颉?/p>

說(shuō)明 :

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

思路一：排序+雙指針

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

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;}}//如果是單調(diào)遞增,不需要修改，返回0if(left_index == -1) return 0;//如果是單調(diào)遞減，返回整個(gè)長(zhǎng)度if(right_index == -1) return nums.size();return (right_index - left_index + 1);} };

思路二：單調(diào)棧

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

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;} };

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

這一題的雙指針解法和接雨水的雙指針?biāo)枷胗幸欢ㄏ嗨菩?#xff1a;
leetcode 42. 接雨水 思考分析(暴力、動(dòng)態(tài)規(guī)劃、雙指針、單調(diào)棧)
我們要做的是，找到無(wú)序數(shù)組的上下界。
運(yùn)用到本題，就是下面兩個(gè)想法:
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/
無(wú)序子數(shù)組中最小元素的正確位置可以決定左邊界，最大元素的正確位置可以決定右邊界。
尋找右邊界：
從左往右遍歷，用max記錄遍歷過(guò)的最大值，如果max大于當(dāng)前nums[i]，說(shuō)明nums[i]的位子不正確，屬于需要排序的數(shù)組，所以右邊界就需要更新為i
如果nums[i]大于max更新max，繼續(xù)往右檢查，是否有元素比更新之后的max要小；最終可以找到需要排序的數(shù)組的右邊界，右邊界之后的元素都大于max。
尋找左邊界：
從右向左遍歷，yongmin記錄當(dāng)前遍歷過(guò)的最小值，如果min小于當(dāng)前nums[i]，說(shuō)明nums[i]的位子不正確，屬于需要排序的數(shù)組，所以更新左邊界
如果nums[i]小于min更新min，繼續(xù)往左檢查，是否有元素比更新之后的min要大，最終可以找到需要排序的數(shù)組的左邊界，左邊界之前的元素都小于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;//升序時(shí)移動(dòng) curMin 和 curMax//逆序時(shí)移動(dòng) down 和 up//不論順序如何，雙指針 left 和 rigt 一直保持移動(dòng)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;} };

單調(diào)棧暫時(shí)就刷到這兒，接下來(lái)繼續(xù)刷雙指針的題目吧。

總結(jié)

以上是生活随笔為你收集整理的单调栈 leetcode整理（三）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。