今天繼續(xù)學(xué)習(xí)單調(diào)棧解決相關(guān)問題。

496.下一個更大的元素|

nums1?中數(shù)字?x?的 下一個更大元素 是指?x?在?nums2 中對應(yīng)位置 右側(cè) 的 第一個 比?x?大的元素。

給你兩個 沒有重復(fù)元素 的數(shù)組?nums1 和?nums2 ，下標(biāo)從 0 開始計數(shù)，其中nums1?是?nums2?的子集。

對于每個 0 <= i < nums1.length ，找出滿足 nums1[i] == nums2[j] 的下標(biāo) j ，并且在 nums2 確定 nums2[j] 的 下一個更大元素 。如果不存在下一個更大元素，那么本次查詢的答案是 -1 。

返回一個長度為?nums1.length 的數(shù)組 ans 作為答案，滿足 ans[i] 是如上所述的 下一個更大元素 。

示例 1：

輸入：nums1 = [4,1,2], nums2 = [1,3,4,2].
輸出：[-1,3,-1]
解釋：nums1 中每個值的下一個更大元素如下所述：
- 4 ，用加粗斜體標(biāo)識，nums2 = [1,3,4,2]。不存在下一個更大元素，所以答案是 -1 。
- 1 ，用加粗斜體標(biāo)識，nums2 = [1,3,4,2]。下一個更大元素是 3 。
- 2 ，用加粗斜體標(biāo)識，nums2 = [1,3,4,2]。不存在下一個更大元素，所以答案是 -1 。
示例 2：

輸入：nums1 = [2,4], nums2 = [1,2,3,4].
輸出：[3,-1]
解釋：nums1 中每個值的下一個更大元素如下所述：
- 2 ，用加粗斜體標(biāo)識，nums2 = [1,2,3,4]。下一個更大元素是 3 。
- 4 ，用加粗斜體標(biāo)識，nums2 = [1,2,3,4]。不存在下一個更大元素，所以答案是 -1 。

思路：

1.本題在Day61初次接觸的那道每日溫度的基礎(chǔ)之上稍加變化了一下，原本是只有一個數(shù)組，我們只需要按部就班找到每一個元素右邊第一個比他大的就行，本題則是采用了兩個數(shù)組并且其中一個數(shù)組是另一個數(shù)組的子集，讓我們找子集數(shù)組里面所有元素在另一個數(shù)組里面右邊的第一個比他大的元素。

2.因?yàn)榉殖闪藘蓚€無重復(fù)元素的數(shù)組，因此我們需要建立起兩個數(shù)組之間的聯(lián)系。既然無重復(fù)元素，可以想到利用哈希表來建立映射，以元素值為鍵，以下標(biāo)為值，正好也對應(yīng)上我們用單調(diào)棧存儲的是遍歷過的元素下標(biāo)。

3.單調(diào)棧中依舊采取從棧頭到棧底遞增的順序，這樣才能保證找到的是右邊第一個更大的元素。

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result(nums1.size(), -1);
        stack<int> st;//單調(diào)棧存儲遍歷過的元素下標(biāo)
        unordered_map<int,int> umap;

        //哈希表建立映射，鍵為元素值，值為下標(biāo)
        for(int i = 0; i < nums1.size(); i++){
            umap[nums1[i]] = i;
        }
        st.push(0);

        for(int i = 1; i < nums2.size(); i++){
            if(nums2[i] <= nums2[st.top()]){
                st.push(i);
            }
            else{
                while(!st.empty() && nums2[i] > nums2[st.top()]){
                    //先判斷棧頂元素是否存在于nums1中，如果存在才進(jìn)行結(jié)果存儲
                    if(umap.count(nums2[st.top()])){
                        int index = umap[nums2[st.top()]];
                        result[index] = nums2[i];
                    }
                    //判斷完棧頂元素后要將棧頂元素出棧
                    st.pop();
                }
                st.push(i);
            }
        }

        return result;
    }
};

啟發(fā)：

1.本題將單個數(shù)組拆成了兩個數(shù)組，因此我們需要建立起兩個數(shù)組之間的聯(lián)系進(jìn)一步來轉(zhuǎn)化為類似單個數(shù)組的解題方法。

503.下一個更大元素||

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

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

示例 1:

輸入: nums = [1,2,1]
輸出: [2,-1,2]
解釋: 第一個 1 的下一個更大的數(shù)是 2；
數(shù)字 2 找不到下一個更大的數(shù)；?
第二個 1 的下一個最大的數(shù)需要循環(huán)搜索，結(jié)果也是 2。
示例 2:

輸入: nums = [1,2,3,4,3]
輸出: [2,3,4,-1,4]

思路：

1.本題同樣是在Day61的每日溫度基礎(chǔ)之上進(jìn)行了另一種變化，只有一個數(shù)組但是數(shù)組成環(huán)了。既然成環(huán)了那么就會很容易想到進(jìn)行取模的操作來達(dá)成環(huán)的效果。

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> result(nums.size(), -1);
        stack<int> st;

        st.push(0);
        for(int i = 1; i < nums.size() * 2; i++){
            if(nums[i % nums.size()] <= nums[st.top()]){
                st.push(i % nums.size());
            }
            else{
                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;
    }
};

啟發(fā)：

1.本題其實(shí)細(xì)節(jié)還是不少的，如在for循環(huán)中i的判斷條件，盡管成環(huán)了理論上來說可以無限次循環(huán)整個數(shù)組，但實(shí)際上只要循環(huán)數(shù)組的大小*2就足夠我們找到所有元素的情況了，后續(xù)的循環(huán)沒有意義。

2.本題中result中的元素是否會被后續(xù)成環(huán)后的第二次循環(huán)覆蓋掉呢？其實(shí)并不會，實(shí)際代入幾個結(jié)果模擬后就會發(fā)現(xiàn)盡管第二輪循環(huán)中會將result的值進(jìn)行“改變”，但實(shí)際上對應(yīng)元素賦的都是同一個值，就好像第一次循環(huán)我們找到了每個元素右邊第一大的元素，第二輪循環(huán)我們只是從頭開始又循環(huán)了一次，同樣會找到每個元素右邊第一大的元素（并且這個元素并不會改變）。文章來源地址http://www.zghlxwxcb.cn/news/detail-428617.html

到了這里，關(guān)于代碼隨想錄Day62的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！