栈与队列

栈与队列的设计
LC641 Design Circular Deque
LC155 Min Stack
LC716 Max Stack
LC896 Maximum Frequency Stack
LC232 Implement Queue using Stacks [第二个栈空了，就把第一个导入第二个。不空就从第二个取]
LC225 Implement Stack using Queues

单调队列：
LC239 Sliding Windows Maximum
❓LC861 Shortest Subarray with Sum at Least K[仍然不理解为什么]

简单单调栈（Next Greater Element及其变种）：
LC496 Next Greater Element I
LC503 Next Greater Element II [循环数组]
LC1019 链表中下一个更大节点
LC739 Daily Temperatures
LC901 Online Stock Span

复杂单调栈（面积计算类）：
LC42 Trapping Rain Water [lmr三个一组算trap]
LC84 Largest Rectangle in Histogram [以每个柱子的高，能围成的最大面积]
LC85 Maximal Rectangle [二维柱状图面积]

栈与括号
LC394 Decode String

队列

STL中的双端队列

std::deque, cppreference

• 在 deque 任一端插入或删除不会非法化指向其余元素的指针或引用。

• 与 std::vector 相反， deque 的元素不是相接存储的：典型实现用单独分配的固定大小数组的序列，外加额外的登记，这表示下标访问必须进行二次指针解引用，与之相比 vector 的下标访问只进行一次。

• deque 的存储按需自动扩展及收缩。扩张 deque 比扩展 std::vector 便宜，因为它不涉及到复制既存元素到新内存位置。另一方面， deque 典型地拥有较大的最小内存开销；只保有一个元素的 deque 必须分配其整个内部数组（例如 64 位 libstdc++ 上为对象大小 8 倍； 64 位 libc++ 上为对象大小 16 倍或 4096 字节的较大者）。

• deque在gcc中的实现，类似memory virtualization中的paging。数据被存储在固定大小的”buffer”中（类似一个page），”buffer”的首地址被一个”map”数组记录（类似一个page table）。
• deque的”buffer”大小不可指定。gcc为其对象大小8倍，也就是说，一个buffer可以储存8个元素。stackoverflow: Why doesn’t std::deque allow specifying the bucket size?
• deque因为其类似paging的内存管理机制，所以没有reserve()。
• deque的迭代器虽然是RandomAccessIterator, 但因为引入了一层间接，导致下标访问需要先已通过map找到buffer，再通过偏移量找到数据。因此效率较差。

简单实现一个双端队列

通过循环数组简单实现一个双端队列。该双端队列为固定大小，不需要实现扩张。

LC641, Design Circular Deque

code

class MyCircularDeque {
private:
    size_t cap;
    size_t size;
    int* array;
    int* first;
    int* last;
    
    int* circlePointer(int* p)
    {
        if (p < array) return array + cap - 1;
        if (p > array + cap - 1) return array;
        return p;
    }
    
    int* nextFirst()
    {
        return circlePointer(first - 1);
    }
    
    int* prevFirst()
    {
        return circlePointer(first + 1);
    }
    
    int* nextLast()
    {
        return circlePointer(last + 1);
    }
    
    int* prevLast()
    {
        return circlePointer(last - 1);
    }
    
public:
    /** Initialize your data structure here. Set the size of the deque to be k. */
    MyCircularDeque(int k):
    cap(k),
    size(0),
    array(new int[k]),
    first(array),
    last(array + 1)
    {}
    
    ~MyCircularDeque()
    {
        //We are not responsible for deleteing all the objects in the array. Before calling the dtor of this class, clients should do it instead.
        delete[] array;
    }
    
    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    bool insertLast(int value) {
        if (isFull()) return false;
        *first = value;
        ++size;
        first = nextFirst();
        return true;
    }
    
    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    bool insertFront(int value) {
        if (isFull()) return false;
        *last = value;
        ++size;
        last = nextLast();
        return true;
    }
    
    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    bool deleteLast() {
        if (isEmpty()) return false;
        first = prevFirst();
        --size;
        return true;
        
    }
    
    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    bool deleteFront() {
        if (isEmpty()) return false;
        last = prevLast();
        --size;
        return true;
    }
    
    /** Get the front item from the deque. */
    int getRear() {
        if(isEmpty()) return -1;
        return *prevFirst();
    }
    
    /** Get the last item from the deque. */
    int getFront() {
        if(isEmpty()) return -1;
        return *prevLast();
    }
    
    /** Checks whether the circular deque is empty or not. */
    bool isEmpty() {
        return size == 0;
    }
    
    /** Checks whether the circular deque is full or not. */
    bool isFull() {
        return size == cap;
    }
};

更好的实现: boost: circular_buffer

用栈实现队列

LC232, Implement Queue using Stacks

• 使用两个栈
• 一个栈(stack1)用来存储新push进来的数据
• 另一个栈(stack2)用来reverse第一个栈里的数据
• 每次pop的时候，检查stack2是否为空，如果为空，就把stack1里面的全部数据都pop再push进stack2。如果不为空就直接从stack2栈顶取一个数据返回即可。

code

class MyQueue {
private:
    stack<int> s1;
    stack<int> s2;
public:
    /** Initialize your data structure here. */
    MyQueue():
    s1{},
    s2{} 
    {}
    
    /** Push element x to the back of queue. */
    void push(int x) {
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int res = peek();
        s2.pop();
        return res;
    }
    
    /** Get the front element. */
    int peek() {
        if(s2.empty())
        {
            while(!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
        }

        return s2.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return s1.empty() && s2.empty();
    }
};

单调队列

滑动窗口最大值

LC239 Sliding Windows Maximum

思路：

• 维护元素进入队列时间的单调性，即队列中元素从头到尾进入队列时间递增。因此该队列只能从队尾加入元素。
• 维护元素大小的单调性，即队列中元素从头到尾是递减的。因此必要时可以从队尾删除元素。
• 维护队列的长度，即从队伍头部删除过期的元素。

实现：

• 队首队尾都要做删除，因为可以用Doubly Linked List 或者 Deque 实现
• 每次向队伍里放置一个新元素，先把他和队尾不断比较，删掉所有比他小的队尾，然后将它放到队尾。
• 检查一下队首是不是过期了。

code

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        auto q = deque<decltype(nums.begin())>{};
        auto res = vector<int>{};

        for(auto it = nums.begin(); it < nums.end(); ++it)
        {
            while(!q.empty() && *it > *q.back())
            {
                q.pop_back();
            }
            q.push_back(it);

            while(q.back() - q.front() + 1 > k)
            {
                q.pop_front();
            }

            if(it - nums.begin() + 1 >= k)
            {
                res.push_back(*q.front());
            }
        }

        return res;

    }
};

和至少为K的最短子数组

LC861, Shortest Subarray with Sum at Least K

• 设数组a的前缀和为p[i] = a[i] + a[i - 1] + … + a[0]
• 则数组a的子数组a[x…y], y > x, 的和可以表示为: s[x…y] = p[y] - p[x]
• 题目要求和至少为k, 即p[y] - p[x] >= k.
• 设对于一个确定y, 使得和至少为k的子数组长度最短的x为x_t.

• 则对于所有的y，如果存在x_t，求这些(y-x_t)当中的最小值.

• 如果x1 < x2 且 p[x1] >= p[x2]:

  • p[y] - p[x1] >= k ==> p[y] - p[x2] >= k
  • y - x1 > y - x2
    因此x1可以被舍弃掉
• 如果 x = x_t 使得 p[y] - p[x] >= k: 即使p[y + m] - p[x] >= k, 也有 y + m - x > y - x. 因此该x可以被舍弃掉。

计算数组的前缀和数组，并维护一个单调递增队列，遍历前缀和数组：

• 每次新遇到的元素的下标必然大于已经在数组中元素的下标，因此如果新遇到的元素y <= 队尾元素x，就一定有式子p[x] >= p[y] 且 x < y 成立。则此时的队尾元素是无用的，丢弃即可。
• ❓每次新遇到的元素y如果减去队首元素x(队中最小元素)>=k，则有式子 p[y] - p[x] >= k 且 y > x存在。则x可以被舍弃掉。舍弃前计算这个满足条件的区间长度。

code

class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        std::deque<std::vector<int>::iterator> deque{};
        std::vector<int> prefixSum{};
        int minDistance = UINT32_MAX;
        computePrefixSum(A,prefixSum);
        for(auto it = prefixSum.begin(); it != prefixSum.end(); ++it)
        {
            while(!deque.empty() && *deque.back() >= *it)
                deque.pop_back();
            while(!deque.empty() && *it - *deque.front() >= K)
            {
                size_t curDis = std::distance(deque.front(), it);
                minDistance = curDis < minDistance ? curDis : minDistance;
                deque.pop_front();
            }
            deque.push_back(it);
        }

        return minDistance == UINT32_MAX ? -1 : static_cast<int>(minDistance);
    }

    void computePrefixSum(const std::vector<int>& A, std::vector<int>& res)
    {
        int sum = 0;
        res.push_back(0);
        std::transform( A.begin(),
                        A.end(),
                        std::back_inserter(res),
                        [&sum](int x){sum += x;return sum;}
        );
    }
};

栈

STL中的栈

• 默认的底层容器为std::deque
• 无法实现异常安全的，能够返回值的pop()方法。Why doesn’t std::queue::pop return value?

用队列实现栈

LC225, Implement Stack using Queues

使用两个队列，将他们记为q1和q2：

• 要插入元素时，将元素放入队列q1
• 要pop元素时，将q1中的元素出队并放入q2，直到只剩下一个元素。记下该元素的值v并pop掉该元素。返回v。此时q1为空，q2中仍有元素。记q1为q2，q2为q1。

code

class MyStack {
private:
    queue<int>* q1;
    queue<int>* q2;
public:
    /** Initialize your data structure here. */
    MyStack()
    :q1(new queue<int>{})
    ,q2(new queue<int>{})
    {}
    
    ~MyStack()
    {
        delete q1;
        delete q2;
    }

    /** Push element x onto stack. */
    void push(int x) {
        q1->push(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        while(q1->size() > 1)
        {
            q2->push(q1->front());
            q1->pop();
        }
        auto val = q1->front();
        q1->pop();
        swap(q1, q2);
        return val;
    }
    
    /** Get the top element. */
    int top() {
        return q1->back();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return q1->empty();
    }
};

最小栈

LC155, Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
思路：

• 使用另一个栈(s2)来记录最小值：
  • 每次push(x)时，比较x和s2.top()，如果x < s2.top()，那么把x放在s2栈顶。否则把s2.top()放在s2栈顶。

Code

class MinStack {
private:
    stack<int> s1;
    stack<int> s2;
public:
    MinStack():
    s1{},
    s2{}
    {}
    
    void push(int x) {
        s1.push(x);
        if (s2.empty() || x < s2.top()) s2.push(x);
        else s2.push(s2.top());
    }
    
    void pop() {
        s1.pop();
        s2.pop();
    }
    
    int top() {
        return s1.top();
    }

    int getMin() {
        return s2.top();
    }
};

最大栈

LC716 Max Stack

和最小栈的区别在于要求实现一个popMax()的功能。简单的思路是模仿minStack，使用两个栈，并在popMax()的时候让真实的栈一直pop()到和min栈的top()相等，再push放回去。另一种想法是用一个multiset来作为查询最大值的数据结构。

//TODO: refactor the code
//TODO: why cannot use find_if?

version: multiset

class MaxStack {
private:
    using It = list<int>::iterator;
    inline static auto cmp =
            [](auto lhs, auto rhs){return *lhs < *rhs;};
    list<int> l;
    multiset<It, decltype(cmp)> maxSet;
public:
    MaxStack():
            l{},
            maxSet{cmp}
    {}

    void push(int x) {
        l.push_front(x);
        maxSet.insert(l.begin());
    }

    int pop() {
        auto range = maxSet.equal_range(l.begin());
        auto it = range.first;
        for(;*it != l.begin();++it);
        maxSet.erase(it);
        int top = l.front();
        l.pop_front();
        return top;
    }

    int top() {
        return l.front();
    }

    int peekMax() {
        return **(--maxSet.end());
    }

    int popMax() {
        auto maxIt = (--maxSet.end());
        auto max = **maxIt;
        l.erase(*maxIt);
        maxSet.erase(maxIt);
        return max;
    }
};

最大频率栈

LC896, Maximum Frequency Stack
//TODO: 详细思路

• 使用一个hashmap来记录每个key的频率【keyFreqMap】
• 使用另一个hashmap来记录每个频率对应的栈【FreqStackMap】
• 每次在push一个key进来的时候，查hashmap找频率，再把他push到该频率对应的栈里
• 每次在pop的时候，都从最大的频率的栈keyFreqMap[keyFreqMap.size()]的顶端pop出一个key，再将该key对应的频率减少1--FreqStackMap[key]即可。如果这个频率对应的栈空了，就给他删除。

code

class FreqStack {
private:
    unordered_map<int, int> freq;
    unordered_map<int, stack<int>*> freqMap;
public:
    FreqStack():
            freq{},
            freqMap{}
    {}

    void push(int x) {
        // we update the freq map
        // if we cannot find the key, initialize it
        if(freq.find(x) == freq.end())
        {
            freq[x] = 1;
        }
        else// the key could be found.
        {
            ++freq[x];
        }
        assert(freq[x] != 0);
        // check if the freq stack of this freq is initilized
        if(freqMap.find(freq[x]) == freqMap.end())
            freqMap[freq[x]] = new stack<int>{{x}};
        else
            freqMap[freq[x]]->push(x);
    }

    int pop() {
        auto maxFreqStack = freqMap[freqMap.size()];
        int res = maxFreqStack->top();
        maxFreqStack->pop();
        --freq[res];
        if(maxFreqStack->empty()){
            freqMap.erase(freqMap.find(freqMap.size()));
            delete maxFreqStack;
        }
        return res;
    }
};

栈用来实现二叉树的遍历

见二叉树

栈与括号

LC394, Decode String

code

class Solution {
private:
    constexpr static char ASCII_0 = 48;
    constexpr static char ASCII_LEFT_BRACKET = 91;
    constexpr static char ASCII_RIGHT_BRACKET = 93;
    using numStringPair = pair<int, string>;
public:
    string decodeString(string s) {
        vector<numStringPair> stack{};
        stack.emplace_back(1, string{});

        auto toDigit = [](char c)->int{return c - ASCII_0;};

        for (auto i = s.begin(); i != s.end(); ++i)
        {
            if(isdigit(*i))
            {
                string num{};
                while(isdigit(*i))
                {
                    num.push_back(*i);
                    ++i;
                }
                stack.emplace_back(atoi(num.c_str()), string{});
                continue;
            }
            else if(*i == ASCII_LEFT_BRACKET)
            {
                // skip the '[', it is useless.
                continue;
            }
            else if(*i == ASCII_RIGHT_BRACKET)
            {
                // append N copies of stack.top().second()
                // to the numStringPair before stack.top()

                auto topIt     = --stack.end();
                auto nextTopIt = topIt - 1;

                for (int j = 0; j < topIt->first; ++j)
                {
                    nextTopIt->second.append(topIt->second);
                }

                stack.pop_back();
            }
            else // i is a letter
            {
                stack.back().second.push_back(*i);
            }
        }
        // now there should be only one string in the stack
        assert(stack.size() == 1);
        return stack.front().second;
    }
};

单调栈

考虑一个递增栈，设栈顶元素为t，将要推入栈中的元素为n

- 1: 如果 n > t， 将 n 推入栈中。此时 t 是 n 左侧第一个比他小的元素。
- 2: 否则， 将栈顶t弹出，如果栈非空，设新的栈顶为t2
    - t2 是 t **左侧第一个比他小的元素**
    - n  是 t **右侧第一个比他小的元素**
- 回到1

考虑一个递减栈，设栈顶元素为t，将要推入栈中的元素为n

- 如果 n < t，将 n 推入栈中。此时 t 是 n 左侧第一个比他大的元素
- 否则，将栈顶t弹出，如果栈非空，设新的栈顶为t2
    - t2 是 t **左侧第一个比他大的元素**
    - n  是 t **右侧第一个比他大的元素**

栈里一般存放元素的指针或者元素的index。需要弹出栈中元素，一般也是用来计算的结果的时候。

单调递增栈，栈内元素的性质图解：
单调递增栈栈内两个相邻的元素$ay > a_x, y > x$，在其原来的数组中，$a_y$和$a_x$之间的元素都在$(a_y, +\infty)$的范围内。即他们之间的元素$a{i}, i \in (x, y)$，必然有$a_{i} > a_y$

                        +-+
                        | |
                        | |
                      +-+ |
                      | | +-+  ^
                      | | | |  |
  +-+- - - - - - - - - - - - - - -+-+
  | |                 | | | |     | |
  | |                 | | | |     | |
  | |                 | | | |     | |
  | |                 | | | |     | |
  | |                 | | | |     | |
+-+ |  +----> +-+     | | | |     | |
| | |         | |     | | | |     | |
| | |         | | ... | | | | ... | |
| | |         | |     | | | |     | |
| | |         | |     | | | |     | |
+---+         +-+     +-----+     +-+

单调递减栈，栈内元素性质图解：
单调递减栈栈内两个相邻的元素$ay < a_x, y > x$，在其原来的数组中，$a_y$和$a_x$之间的元素都在$(-\infty, a_y)$的范围内。即他们之间的元素$a{i}, i \in (x, y)$，必然有$a_{i} < a_y$

+-+          +-+
| |          | |
| |          | |
| |          | |
| |          | |
| |          | |
| +-+ +----> | |- - - - - - - - - -+-+
| | |        | |     +-+ +-+    |  | |
| | |        | |     | | | +-+  v  | |
| | |        | | ... | +-+ | | ... | |
| | |        | |     | | | | |     | |
+-+-+        +-+     +-+-+-+-+     +-+

参考:

• Leetcode 单调栈问题总结,coordinate_blog, csdn
• 刷题笔记6（浅谈单调栈）, 法号桑菜, 知乎

简单单调栈

LC496, Next Greater Element I

先不管数组nums1。维护一个单调递减栈，并在nums2上进行遍历。

• 如果栈为空，将当前数字入栈
• 如果栈非空
  • 检查当前元素是否大于栈顶元素，如果大于栈顶元素则说明当前元素为栈顶元素的下一个更大元素，将对应关系记录在一个hashmap中。并将栈顶元素pop出栈。循环直到栈顶元素大于大于当前元素 或 栈为空。
  • 将当前元素入栈。
• 根据hashmap，找到nums1当中对应的下一更大元素。

code

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> monoStack{};
        unordered_map<int, int> nextGreater{};

        for(int n : nums2)
        {
            while (!monoStack.empty() && monoStack.top() < n)
            {
                nextGreater[monoStack.top()] = n;
                monoStack.pop();
            }
            monoStack.push(n);
        }

        while(!monoStack.empty())
        {
            nextGreater[monoStack.top()] = -1;
            monoStack.pop();
        }

        vector<int> res{};
        transform(nums1.begin(), nums1.end(), back_inserter(res), [&nextGreater](int num){
            return nextGreater[num];
        });

        return res;
    }
};

---

LC503, Next Greater Element II

解法同上，用mod运算将数组”模拟”成循环数组就可以了。

Feb/19/2020 code

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

        for(size_t ii = 0; ii < nums.size() * 2; ++ii)
        {
            auto i = ii % nums.size();
            while (!monoStack.empty() && 
            nums[monoStack.top()] < nums[i])
            {
                res[monoStack.top()] = nums[i];
                monoStack.pop();
            }
            monoStack.push(i);
        }
        return res;        
    }
};

---

LC1019 链表中下一个更大节点
简单的单调栈应用。

class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {

        const auto len = [head]()mutable
        {
            auto cnt = size_t{};
            while(head)
            {
                head = head->next;
                ++cnt;
            }
            return cnt;
        }();

        auto s = stack<ListNode*>{};
        auto m = unordered_map<ListNode*, size_t>{};
        auto res = vector<int>(len);
        auto cnt = size_t{};

        while(head)
        {
            // put it into the map
            m[head] = cnt++;

            auto val = head->val;

            while(!s.empty() && val > s.top()->val)
            {
                res[m[s.top()]] = val;
                s.pop();
            }
            s.push(head);
            head = head->next;
        }

        while(!s.empty())
        {
            res[m[s.top()]] = 0;
            s.pop();
        }

        return res;
    }
};

---

LC739, Daily Temperatures

套壳的下一个更大数字。只不过求的不是数字，而是距离。用一个递减栈存迭代器即可解决。

code

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temps) {
        vector<int> waitDays(temps.size(), 0);
        stack<vector<int>::iterator> monoStack{};

        for(auto it = temps.begin(); it != temps.end(); ++it)
        {
            while (!monoStack.empty() && *monoStack.top() < *it)
            {
                auto day = monoStack.top();
                waitDays[distance(temps.begin(), day)] = distance(day, it);
                monoStack.pop();
            }
            monoStack.push(it);
        } 
        return waitDays;
    }
};

---

LC901, Online Stock Span

• 遇到的每一元素初始化为pair<price, span = 1>
• 维护一个递减栈，每当遇到大于栈顶的元素时，将该栈顶元素出栈，并将出栈的元素的span加到该元素身上。之后再将这个元素放回栈中。之后返回这个元素的span
  code

  class StockSpanner {
  private:
      struct elem
      {
          int price;
          int span;
  
          elem(int price)
          :price(price)
          ,span(1)
          {}
      };
  
      vector<elem> monoStack;
  public:
      StockSpanner() 
      :monoStack{}
      {}
      
      int next(int price) {
          auto cur_elem = elem{price};
          while(!monoStack.empty() && monoStack.back().price <= cur_elem.price)
          {
              cur_elem.span += monoStack.back().span;
              monoStack.pop_back();
          }
  
          monoStack.emplace_back(move(cur_elem));
  
          return monoStack.back().span;
      }
  };

复杂单调栈

LC42, Trapping Rain Water

只有凹进去的地方才能储存雨水。递减栈每次需要弹出的时候，【新的元素，栈顶，栈顶下面一个元素】正好是一个坑。考虑用一个递减栈来计算雨水。

思路参考：windliang, 详细通俗的思路分析，多解法, lc42 solutions

仍然是以个next greater element问题，但计算凹进去部分的存水比较麻烦。

当遇到需要我们出栈的元素时，我们需要三个一组来计算存水

• 记当前元素为r，从栈里pop出一个元素，记为m
• 如果此时栈空了，证明m左边已经没有能挡水的板了，存不住水了，所以直接退出循环。
• 如果此时栈里还有元素，将该元素出栈，记为l
• 我们的任务就是计算(r,m,l)这个三元组能存多少水：
  • m 比 r 先出栈，所以一定有 m < r, 我们又知道 m < l，但是我们不知道r和l的关系，有可能l比r大。所以我们不可以在这个时候把lpop出栈。
  • 存水的多少 = (distance(l, r) - 1) * (min(*l, *r) - *m)。即只计算比中间挡板高的存水。比中间挡板低的存水在之前一定已经计算过了。

Feb/19/2020 code

class Solution {
public:
    int trap(vector<int>& height) {
        height.push_back(0);
        auto monoStack = vector<vector<int>::iterator>{};
        int res = 0;

        for(auto it = height.begin(); it < height.end(); ++it)
        {     
            while(!monoStack.empty() && *monoStack.back() < *it)
            {
                auto mid = monoStack.back();
                monoStack.pop_back();
                // if there is no more element on the left, we can trap any water.
                if(monoStack.empty()) break;
                auto left = monoStack.back();
                // compute how many water it could trap
                res += (it - left - 1) * (min(*it, *left) - *mid);
            }
            monoStack.push_back(it);
        }

        return res;
    }
};

code

class Solution {
public:
    int trap(vector<int>& height) {
        stack<vector<int>::iterator> s{};
        int res = 0;
        for(auto it = height.begin(); it != height.end(); ++it)
        {
            while (!s.empty() && *s.top() < *it )
            {
                auto r = it;
                auto m = s.top();
                s.pop();
                if (s.empty()) {s.push(it);break;}
                auto l = s.top();
                res += computeTrap(l, m, r);
            }
            s.push(it);
        }
        return res;
    }
    template<typename It>
    int computeTrap(It l, It m, It r)
    {
        int width = distance(l,r) - 1;
        int height = min(*l,*r) - *m;
        return width * height;
    }
};

---

LC84, Largest Rectangle in Histogram

算出所有以每个柱的顶部为上边界的最大的矩形的面积，再从中找到最大的面积，即为所求。
为了找到以柱a的顶部为上边的最大矩形面积，我需要确定这个矩形的左右边界。因此我们需要找到柱a左边第一个比柱a矮的柱(记为柱l)，以及柱a右边第一个比柱a高的柱(记为柱r)。因此问题就抽象为：找到每一个数字左右第一个比它小的数字。

自然想到使用一个递增栈来完成：

- 每次遇到比栈顶元素(t)小的元素(i)-->相当于给栈中的所有元素找到了矩形右边界(i)-->左边界也在栈中(把t从栈中pop掉后新的栈顶，t2)-->可以计算矩形面积了。
    矩形面积 = (distance(t, i) - 1) * 柱高
- 假设我们在所有柱子的左侧和右侧都添加一个高度为0的柱。
    - 如果pop掉t后栈空了，左边界就是那个高度为0的最左侧的柱子。
    - 最后一个高度为0的柱子用来帮助把在栈中，没有计算矩形面积的柱的最大矩形面积计算出来。

2020/7/10 code

class Solution {
public:
    int largestRectangleArea(vector<int>& h) {
        h.push_back(0);
        auto s = vector<decltype(h.begin())>{};
        auto res = ptrdiff_t{};
        for(auto i = h.begin(); i < h.end(); ++i)
        {
            while(!s.empty() && *i < *s.back())
            {
                if(s.size() == 1)
                {
                    res = max(res, 
                        (i - h.begin()) * *s.back());
                }
                else
                {
                    res = max(res,
                        (i - *(s.end() - 2) - 1) * *s.back());
                }

                s.pop_back();
            }

            s.push_back(i);
        }
        return res;
    }
};

---

LC85, Maximal Rectangle

将二维数组的每一行都变成一个柱状图，然后用LC84, Largest Rectangle in Histogram的思路求解即可。

详细通俗的思路分析，多解法, windliang, leetcode

code

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix.front().empty()) return 0;
        // build the histograms 
        vector<vector<size_t>> histograms(matrix.size(), vector<size_t>(matrix[0].size()));
        // put the first row into the histogram.
        for(size_t i = 0; i < matrix[0].size(); ++i)
        {
            histograms[0][i] = matrix[0][i] == '1' ? 1 : 0;
        }

        for(size_t i = 1; i < matrix.size(); ++i)
        {
            for(size_t j = 0; j < matrix[i].size(); ++j)
            {
                histograms[i][j] = matrix[i][j] == '0' ? 0 : histograms[i - 1][j] + 1;
            }
        }
        int maxRectArea = 0;
        for (auto& histogram : histograms)
        {
            maxRectArea = max(maxRectArea, maximalRectangleInHistogram(histogram));
        }
        return maxRectArea;
    }

    int maximalRectangleInHistogram(vector<size_t>& histogram)
    {
        // put the guard into the back of the histogram.
        histogram.push_back(0);
        // monoStack
        stack<vector<size_t>::iterator> stack{};
        size_t rectArea = 0;

        for(auto it = histogram.begin(); it != histogram.end(); ++it)
        {
            // violation of increasing order.
            while(!stack.empty() && *it < *stack.top())
            {
                auto topIt = stack.top();
                stack.pop();

                // the leftBound is the "element" before begin.
                if(stack.empty())
                {
                    rectArea = max(rectArea, distance(histogram.begin(), it) * (*topIt));
                }
                // the leftBound is the top element of the stack.
                else
                {
                    rectArea = max(rectArea, (distance(stack.top(), it) - 1) * (*topIt));
                }

            }

            stack.push(it);
        }

        return static_cast<int>(rectArea);

    }
};