496. Next Greater Element I && II && III

這題一開始我覺得超白吃的, 馬上就想到O(n²)的方法,

但後來看完討論, 發現白癡的是我

有一個很神奇的作法, 準備一個stack, 對於要查找的數字, 我們都把他丟進去, 不一樣的是在每次丟進之前, 我們先檢查當前數字是否大於stack最上層的數字, 如果是, 代表他後面的順位就是這個人, 馬上用表紀錄下來後, 就把stack最上層給清掉, 一路就清到沒得清為止,

接著我們只要在用這張表, 對一下就好了, 太猛了這想法, O(n)

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        unordered_map<int, int> m;
        for(auto n: nums2){
            while(st.size() && st.top() < n){
                m[st.top()] = n;
                st.pop();
            }
            st.push(n);
        }
        vector<int> res;
        for(auto i: nums1){
            if(m.count(i)){
                res.push_back(m[i]);
            }else{
                res.push_back(-1);
            }
        }
        return res;
    }
};

2的方式更屌了

變成循環到底怎麼辦, 還要考慮很多東西, 別怕, 把原本的陣列複製一次不就解決了, 另外第二輪的就不要再推進stack裡了, 否則真正要找的那個還是會被第二輪的人擋掉

另外這次因為不是唯一的了, 所以有可能會遇到同樣的數字後面不重複, 所以不要再用unordered_map

改用vector直接紀錄

這真的驚豔

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> res(nums.size(), -1);
        int n = nums.size();
        stack<int> st;
        int i = 0;
        for(; i < 2 * n;i++){
            int index = i % n;
            while(st.size() && nums[st.top()] < nums[index]){
                res[st.top()] = nums[index];
                st.pop();
            }
            if(i < n)
                st.push(i);
        }
        return res;
    }
};

我覺得這三個組合題真的蠻難的

第三個在問, 下一個大的數字組合, 說明就請看題目了

簡單來說, 1234的下一個是誰, 是1243, 這一定要先搞懂, 不然題目根本無法做

125433->132345

首先我們先從後面往回找, 找到唯一變成升序的index_a, 一旦掃完發現沒有, 就是回傳1

再來我們從後面找到一個剛好大於index_a的值, 並把他們做交換

最後再將後方的值進行一次sort, 為什麼要sort, 可以看一下上面的例子就馬上體會了, 簡單來說, 後方組合的最小值一定就是由小到大的值

最後還要檢查, 是否大於INT_MAX 大於一樣回傳-1

class Solution {
public:
    int nextGreaterElement(int n) {
        string numstr = to_string(n);
        if(numstr.size() ==1) return -1;
        stack<char> st;
        int len = numstr.size();
        int i =  len - 2;
        for(; i >= 0;i--){
            if(numstr[i]  < numstr[i + 1]){
                break;
            }
        }
        if(i == -1){
            return -1;
        }
        for(int j = len - 1; j >= i; j--){
            if(numstr[j] > numstr[i]){
                swap(numstr[j], numstr[i]);
                break;
            }
        }
        sort(numstr.begin() + i + 1, numstr.end());
        long res = stol(numstr);
        return res > INT_MAX ? -1: (int)res;
    }
};