c++下推栈 | #接雨水问题#

因为要获取栈底元素大小，STL没有相关函数，则自定义了一个栈，增加getFirst函数。

private:
    int size;
    int* s;
    int index;
public:
    void init(int n) {
        size = n;
        s = new int[n + 1];
        index = 0;
    }
    
    void push(int item) {
        s[index++] = item;
    }
    
    void pop() {
        if (index > 0) {
            index--;
        }
    }
    
    int top() {
        return s[index - 1];
    }
    
    bool empty() {
        return index == 0;
    }
    
    int getFirst() {
        return s[0];
    }
};

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        MyStack s;
        s.init(arr.size());
        long long ans = 0;
        for (int item: arr) {
            if (s.empty() == true) {
                s.push(item);
                continue;
            }
            
            if (item <= s.top()) {
                s.push(item);
            } else {
                int count = 0;
                int hight = min(item, s.getFirst());
                while (!s.empty() && s.top() < item) {
                    ans += (hight - s.top());
                    s.pop();
                    count++;
                }
                
                if (s.empty() == true) {
                    s.push(item);
                } else {
                    while (count-- >= 0) {
                        s.push(item);
                    }
                }
            }
        }
        
        return ans;
    }
};