Re: [閒聊] 每日leetcode

[eden6197 (:))]

155. MinStack

題目:
希望你完成一個stack
可以pop push
同時可以知道裡面的最小值

思路：
因為要知道最小值
所以如果直接用一個stack紀錄值
喔個monotonic stack紀錄最小值的話
可能會出現一種情況
有重複數字出現
pop之後 數字沒了
min值也被pop掉的情況

所以就改用再多一個vector
記錄index對應的值

然後在stack裡面就用值來push pop

不過看解答後發現 其實
minstack也可以讓他==的時候也放進去
也會對就是了 因為就允許重複了



```cpp
class MinStack {
public:

    vector<int> save;
    vector<int> paper;
    vector<int> minpaper;


    MinStack() {
        paper.clear();
        save.clear();
        minpaper.clear();
    }

    void push(int val)
    {
        save.push_back(val);

        minpaper.push_back(save.size()-1);
        while(minpaper.size()>1 && save[minpaper[minpaper.size()-1]] > save[mi
np
aper[minpaper.size()-2]])
        {
            minpaper.pop_back();
        }
        paper.push_back(save.size()-1);
    }

    void pop() {
        if(minpaper.back() == paper.back())
        {
            minpaper.pop_back();
        }
        paper.pop_back();
    }

    int top()
    {

        return save[paper.back()];

    }

    int getMin()
    {

        return save[minpaper.back()];

    }
};

```

--

https://i.imgur.com/xkznRtr.jpeg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.0.146 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722692915.A.A0F.html
推 CanIndulgeMe: 技術大神
→ itoumashiro: 斜槓雞哥
推 sustainer123: 雞哥要進姑姑嚕了
推 DJYOMIYAHINA: 大師...
推 nh60211as: 大師
→ NCKUEECS: 又會做菜又會刷題
推 WindSpread: 導致程序出包了
推 sixB: 不是 為啥ㄐㄍ會刷題 能不能給點活路
推 sixB: 這個有sort過嗎？？