單調堆疊佇列

發表於 | 分類於 ，

monotonic stack

觀念

這個要用monotonic stack，我刷題目下來，這類monotonic stack 我覺得稍微困難，意思大概就是維護一個stack，每當number push into stack，會比較stack.top()，大於或小於(是大於還是小於看應用)，使得stack 裡面呈現monotonic ，所以稱之 monotonic stack。

  • monotonic stack
1
2
3
4
5
6
while (!s.empty() && s.top() <= nums[i]) {
    // 将前面小于自己的元素都删除
    // 矮个起开，反正也被挡着了。。。
    s.pop();
    }

題目

  • 496 Next Greater Element I (Medium)
  • 503 Next Greater Element II (Medium)
  • 739 Daily Temperatures (Medium)
  • 316 Remove Duplicate Letters (Medium)
  • 1081 Smallest Subsequence of Distinct Characters (Medium)
  • 42 Trapping Rain Water (Hard)
  • *316 Remove Duplicate Letters (Medium)
  • *1081 Smallest Subsequence of Distinct Characters (Medium)

補充

  • 402 Remove K Digits
  • 1019 Next Greater Node In Linked List (Medium)
  • 901 Online Stock Span (Medium)
  • 402 Remove K Digits (Medium)
  • 84 Largest Rectangle in Histogram (Hard)

    85 Maximal Rectangle (Hard)

  • 42 Trapping Rain Water (Hard)
  • 581 Shortest Unsorted Continuous Subarray

monotonic queue

題目

  • 239 Sliding Window Maximum (Hard)

觀念

  • 遞減queue
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class MonotonicQueue {
        // 双链表，支持头部和尾部增删元素
        private LinkedList<Integer> q = new LinkedList<>();

        public void push(int n) {
        // 将前面小于自己的元素都删除
            while (!q.isEmpty() && q.getLast() < n) {
                q.pollLast();
            }
            q.addLast(n);
        }
        public int max(){
            // O(1)
            return q.getFirst();
        }
        public void pop(int n) {
            if (n == q.getFirst()) {
                q.pollFirst();
            }
        }
    }