LeetCode 503- 下一個(gè)更大元素 II

題目鏈接：力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術(shù)成長(zhǎng)平臺(tái)

題目描述：給定一個(gè)循環(huán)數(shù)組 nums （ nums[nums.length - 1] 的下一個(gè)元素是 nums[0] ），返回 nums 中每個(gè)元素的 下一個(gè)更大元素 。

數(shù)字 x 的 下一個(gè)更大的元素 是按數(shù)組遍歷順序，這個(gè)數(shù)字之后的第一個(gè)比它更大的數(shù)，這意味著你應(yīng)該循環(huán)地搜索它的下一個(gè)更大的數(shù)。如果不存在，則輸出 -1 。

解題思路

1. 本題也是單調(diào)棧的一個(gè)應(yīng)用，和溫度那題一模一樣，就是多了一個(gè)循環(huán)，數(shù)組成環(huán)了該怎么處理，首先就想到把給定的數(shù)組和自己拼接起來(lái)，當(dāng)做新的數(shù)組，再用單調(diào)棧操作即可，但這樣會(huì)導(dǎo)致很多冗余的操作。所以想到取余來(lái)算，模擬拼接了數(shù)組的情況。

// 版本二
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> result(nums.size(), -1);
        if (nums.size() == 0) return result;
        stack<int> st;
        for (int i = 0; i < nums.size() * 2; i++) {
            // 模擬遍歷兩邊nums，注意一下都是用i % nums.size()來(lái)操作
            while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {
                result[st.top()] = nums[i % nums.size()];
                st.pop();
            }
            st.push(i % nums.size());
        }
        return result;
    }
};

總結(jié)：

• 單調(diào)棧加環(huán)形數(shù)組的應(yīng)用。

LeetCode 42- 接雨水

題目鏈接：力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術(shù)成長(zhǎng)平臺(tái)

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

解題思路

用單調(diào)棧來(lái)解題，遞增的單調(diào)棧，由于棧頂每次都是最小的元素，我們接雨水其實(shí)就是找中間元素的左邊第一個(gè)比他高的元素和右邊第一個(gè)比他高的元素。右邊第一個(gè)比他高的元素我們可以在入棧之前判斷，而左邊第一個(gè)比他高的元素，就是他在棧中的下面的一個(gè)元素。

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.size() <= 2) return 0; // 可以不加
        stack<int> st; // 存著下標(biāo)，計(jì)算的時(shí)候用下標(biāo)對(duì)應(yīng)的柱子高度
        st.push(0);
        int sum = 0;
        for (int i = 1; i < height.size(); i++) {
            if (height[i] < height[st.top()]) {     // 情況一
                st.push(i);
            } if (height[i] == height[st.top()]) {  // 情況二
                st.pop(); // 其實(shí)這一句可以不加，效果是一樣的，但處理相同的情況的思路卻變了。
                st.push(i);
            } else {                                // 情況三
                while (!st.empty() && height[i] > height[st.top()]) { // 注意這里是while
                    int mid = st.top();
                    st.pop();
                    if (!st.empty()) {
                        int h = min(height[st.top()], height[i]) - height[mid];
                        int w = i - st.top() - 1; // 注意減一，只求中間寬度
                        sum += h * w;
                    }
                }
                st.push(i);
            }
        }
        return sum;
    }
};

總結(jié)：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-708456.html

• 單調(diào)棧的應(yīng)用，需要多想想為什么這里能用到單調(diào)棧。

到了這里，關(guān)于算法|Day51 單調(diào)棧2的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！