Monotonic Stack

Introduce the “small but mighty” algorithm — monotonic stack and its five properties.

• Next Smaller Element
• Previous Not Greater Element
• Minimum in Subarray
• Monotonic Increasing Stack
• Offline RMQ

Discussed the following problems with monotonic stack:

• Find next greater or smaller elements.
• Find subarrays for an element being minimum or maximum.
• Stack-sortable Permutation, 231 Pattern.
• Lexicorgraphically smallest subsequence after removing some elements.

Problem List

496. Next Greater Element I
1019. Next Greater Node In Linked List
503. Next Greater Element II
739. Daily Temperatures
1475. Final Prices With a Special Discount in a Shop
1762. Buildings With an Ocean View
901. Online Stock Span
2334. Subarray With Elements Greater Than Varying Threshold
1944. Number of Visible People in a Queue
42. Trapping Rain Water
84. Largest Rectangle in Histogram
85. Maximal Rectangle
1856. Maximum Subarray Min-Product
1063. Number of Valid Subarrays
907. Sum of Subarray Minimums
456. 132 Pattern
402. Remove K Digits
316. Remove Duplicate Letters
1081. Smallest Subsequence of Distinct Characters
2030. Smallest K-Length Subsequence With Occurrences of a Letter

Introduction to Monotonic Stack

Monotonic Increasing Stack

Definition

For an array A, the length of A is len(A). The monotonic stack S of A is computed by:

• for k in [0, len(A)):
  • while S is not empty and the top element of S S.top has A[S.top] > A[k]:
    • pop the top of S
  • push k to the top of S

Take the array [3, 10, 12, 8, 6, 10] as an example:

        ┌─┐
        │1│
    ┌─┐ │2│         ┌─┐
    │1│ │ │         │1│
    │0│ │ │ ┌─┐     │0│
    │ │ │ │ │8│     │ │
    │ │ │ │ │ │ ┌─┐ │ │
    │ │ │ │ │ │ │6│ │ │
    │ │ │ │ │ │ │ │ │ │
┌─┐ │ │ │ │ │ │ │ │ │ │
│3│ │ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │ │ │ │
└─┘ └─┘ └─┘ └─┘ └─┘ └─┘
 0   1   2   3   4   5
                            ┌─┐
                            │1│
            ┌─┐         ┌─┐ │2│
            │1│         │1│ │ │
            │0│         │0│ │ │
            │ │         │ │ │ │
            │ │         │ │ │ │
            │ │         │ │ │ │
            │ │         │ │ │ │
┌─┐     ┌─┐ │ │     ┌─┐ │ │ │ │
│3│     │3│ │ │     │3│ │ │ │ │
│ │ ──► │ │ │ │ ──► │ │ │ │ │ │
│ │     │ │ │ │     │ │ │ │ │ │
└─┘     └─┘ └─┘     └─┘ └─┘ └─┘
 0       0   1       0   1   2
                                ┌─┐
                                │1│
    ┌─┐                         │0│
    │8│                         │ │
    │ │         ┌─┐         ┌─┐ │ │
    │ │         │6│         │6│ │ │
    │ │         │ │         │ │ │ │
┌─┐ │ │     ┌─┐ │ │     ┌─┐ │ │ │ │
│3│ │ │     │3│ │ │     │3│ │ │ │ │
│ │ │ │ ──► │ │ │ │ ──► │ │ │ │ │ │
│ │ │ │     │ │ │ │     │ │ │ │ │ │
└─┘ └─┘     └─┘ └─┘     └─┘ └─┘ └─┘
 0   3       0   4       0   4   5

1. i = 0, s = []. The stack is empty. No element is popped. 3 is pushed into the stack.
2. i = 1, s = [0]. The top of the stack is 3. A[i] = A[1] = 8 is greater than the top of the stack — A[0] = 3. No element of the stack is popped. 1 is pushed into the stack.
3. i = 2, s = [0, 1]. A[2] = 12 is greater than the top of the stack — A[1] = 8. No element of the stack is popped. 2 is pushed into the stack.
4. i = 3, s = [0, 1, 2]. A[3] = 8 is smaller than the top of the stack — A[2] = 12. Pop 2 out of the stack. The new top of the stack is 1, A[3] = 8 is smaller than the new top of stack — A[1] = 10. Pop 1 out of the stack. The new top of the stack is now 0. A[3] = 8 is now greater than the new top of the stack. Push 3 into the stack.
5. i = 4, s = [0, 3]. A[4] = 6 is smaller than the top of the stack — A[3] = 8. Thus, 3 is popped. A[4] is greater than the new top of the stack — A[0] = 3. Push 4 into the stack.
6. i = 5, s = [0, 4]. A[5] = 10 is greater than the top of the stack — A[4] = 6. Push 5 into the stack.
7. The stack is finally s = [0, 4, 5].

Properties

• When index i in the stack is popped out by index j:

  • PROPERTY 1 - Next Smaller Element(1)
    j is the minimum index such that j > i and A[j] < A[i] (i.e. A[j] is the next smaller element of A[i]).
  • PROPERTY 2 - Previous Not Greater Element
    • After i being popped out
      • if the stack is not empty, the top of the stack h is the maximum index such that h < i and A[h] <= A[a] (i.e. A[h] is the previous not greater element of A[i]).
      • if the stack is empty, there is no index h such that h < i and A[h] < A[a] (i.e. no previous not greater element)
  • PROPERTY 3 - Minimum in Subarray
    • After i being popped out, denote the top of the stack as h
    • the subarray R_[h + 1, j)(if h exists) or the subarray R_[0, j) (if h does not exist) is the subarray of array A such that for all indices k in the subarray R, R[k] >= A[i] (i.e. A[i] is the minimum of the subarray R).
      • However, A[i] might not be the only minimum in the subarray R.
      • Subarray R is the longest subarray such that A[i] is the first minimum.
      • Subarray R might not be the longest subarray that contains A[i] as one of its minimum elements(Their could be multiple minimums with the same value). R is the longest when h does not exist or A[h] < A[a].
    • For two elements (which are indices of array A) in the stack , i and j , i < j. We have A[k] > A[j] >= A[i] for all k in the range (i, j).

• PROPERTY 1 - Next Smaller Element(2) If index i is not popped out after all elements of the array are visited, then there is no j such that j > i and A[j] < A[a] (i.e. A[i] does not have next smaller element)

• After pushing the index k into the stack, denote the elements (which are indices of the array A) in the stack as s_i, where i is in the range [0, len(stack)). We have the following properties:

  • s_(len(stack) - 1) == k (the last element in the stack is k because we have just pushed k onto the top of the stack in the last step of the algorithm).
  • PROPERTY 4 - Monotonic Increasing Stack
    • [A[s_i]] is a subsequence of the original array such that A[s_i] <= A[s_(i - 1)] (non-decreasing subsequence).
    • [s_i] is a subsequence of the indices [0, 1, ... k] such that s_i < s_(i + 1) (strictly increasing indices)
  • PROPERTY 5 - Offline RMQ(Minimum) An RMQ (Range Minimum Query) of the range ends at k (inclusive) could be performed with O(Log(len(stack))) time complexity:
    • To query the minimum of the range [j, k] (j < k), find the first index r in [s_i] such that r >= j, the result of the RMQ is A[r]. Such r could be located with binary search (such as std::lower_bound) because [s_i] is sorted.
    • RMQs of a known set of ranges could be done in O(kLog(N)) where k is the number of ranges and N the length of the array(k < N). This is achieved by:
      • Sort the k ranges by their end, O(kLog(k)).
      • Build the monotonic stack and perform RMQs of the sorted ranges, O(kLog(N)).

The following figures illustrate the 5 properties of the increasing monotonic stack:

• PROPERTY 1 - Next Smaller Element

     ┌───────────┐ PUSH
     │   STACK   │  │
     │      ┌─┐  │  │
     │    ┌─┤ │  │  ▼
─────┼────┤ │ ├──┼─┬─┬─────────────
     │    │ │ │  │ │ │
     │  ┌─┤ │ │  │ │ │
     │  │ │ │ │  │ │ │
     │  │ │ │ │  │ │ │
     │  │ │ │ │  │ │ │
     │  └─┴┬┴┬┘  │ └─┘
     │     │ │   │  ▲
     └──── │ │ ──┘  │
           │ │      │
           │ │      │
           │ │      │
           └─┴──────┘
        NEXT SMALLER ELEMENT

• PROPERTY 2 - Previous Not Greater Element
• PROPERTY 3 - Minimum in Subarray

┌─┐
│*│
│*│
└─┘
 PREVIOUS IN STACK, POPPED OUT
┌─┐
│ │
│ │
└─┘
 IN STACK
        ┌─┐             ┌─┐
        │*│             │*│
    ┌─┐ │*│         ┌─┐ │*│     ┌─┐
    │*│ │*│         │*│ │*│     │*│
    │*│ │*│ ┌─┐     │*│ │*│ ┌─┐ │*│
    │*│ │*│ │*│    ─┤*├─┤*├─┤*├─┤*├─┬─┐
────┤*├─┤*├─┤*├─┬─┐ │*│ │*│ │*│ │*│ │ │
    │*│ │*│ │*│ │ │ │*│ │*│ │*│ │*│ │ │
    │*│ │*│ │*│ │ │ │*│ │*│ │*│ │*│ │ │
┌─┐ │*│ │*│ │*│ │ │ │*│ │*│ │*│ │*│ │ │
│ │ │*│ │*│ │*│ │ │ │*│ │*│ │*│ │*│ │ │
│ │ │*│ │*│ │*│ │ │ │*│ │*│ │*│ │*│ │ │
│ │ │*│ │*│ │*│ │ │ │*│ │*│ │*│ │*│ │ │
└┬┘ └─┘ └─┘ └─┘ └┬┘ └─┘ └─┘ └─┘ └─┘ └─┘
 │ │             │                 │
 │ └◄────────────┼─────────────────┘
 │               │    
 │               │    
 │               │    
 │               ▼
 │               PROP3 : Minimum in Subarray
 ▼
 PROP2: Previous Not Greater Element

• PROPERTY 4 - Monotonic Increasing Stack
• PROPERTY 5 - Offline RMQ(Minimum)

┌─┐
│*│
│*│
└─┘
 PREVIOUS IN STACK, POPPED OUT
┌─┐
│ │
│ │
└─┘
 IN STACK
        ┌─┐             ┌─┐
        │*│             │*│
    ┌─┐ │*│         ┌─┐ │*│     ┌─┐
    │*│ │*│         │*│ │*│     │*│
    │*│ │*│ ┌─┐     │*│ │*│ ┌─┐ │*│
    │*│ │*│ │*│     │*│ │*│ │*│ │*│ ┌─┐
    │*│ │*│ │*│ ┌─┐ │*│ │*│ │*│ │*│ │ │
    │*│ │*│ │*│ │ │ │*│ │*│ │*│ │*│ │ │
    │*│ │*│ │*│ │ │ │*│ │*│ │*│ │*│ │ │
┌─┐ │*│ │*│ │*│ │ │ │*│ │*│ │*│ │*│ │ │
│ │ │*│ │*│ │*│ │ │ │*│ │*│ │*│ │*│ │ │
│ │ │*│ │*│ │*│ │ │ │*│ │*│ │*│ │*│ │ │
│ │ │*│ │*│ │*│ │ │ │*│ │*│ │*│ │*│ │ │
└┬┘ └┬┘ └─┘ └─┘ └┬┘ └┬┘ └─┘ └─┘ └─┘ └┬┘
 │   │           │   │               │
 └───┼───────────┼───┼───────────────┼───► Monotonic Stack
     │           │   │               │
     │           │   │ ---- RMQ?---- │
     │           │   └───────────────┤
     │-------- RMQ? ---------------- │
     └───────────┬───────────────────┤
                 │                   │
                 │                   │
                 ▼                   │
               RMQ RESULT            ▼
                                   RMQ RESULT

Monotonic Decreasing Stack

Definition

monotonic decreasing stack is similar to the monotonic increasing stack. However, the top of the stack is popped when A[S.top] < A[k]

For an array A, a monotonic stack S is a subsequence of the indices array [0, 1, 2, ... j), such that S is built by:

• for k in [0, j):
  • while S is not empty and the top of S has A[S.top] < A[k]:
    • pop the top of S
  • push i to the top of S

Properties

The properties of the decreasing monotonic stack could be derived by reversing the 5 properties of the increasing monotonic stack.

Usage

Next Greater/Smaller Element

496. Next Greater Element I
1019. Next Greater Node In Linked List
503. Next Greater Element II
739. Daily Temperatures
1475. Final Prices With a Special Discount in a Shop
1762. Buildings With an Ocean View

---

496. Next Greater Element I

[496. Next Greater Element I]

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
      auto nextGreaters = std::unordered_map<int, int>();
      auto s = std::vector<int>{};
      for(auto n : nums2) {        
        while(!s.empty() && s.back() < n) {
          nextGreaters[s.back()] = n;
          s.pop_back();
        }
        // s.empty() || s.back() >= n
        s.push_back(n);
      }
      for(auto& n : nums1) {
        if(auto it = nextGreaters.find(n);
            it != nextGreaters.end()) {
          n = it->second;
        } else {
          n = -1;
        }
      }
      return nums1;
    }
};

This problem uses PROPERTY 1 - Next Smaller(Greater) Element. The name of the problem is self-explanatory. It’s a nice idea to use it to test your code template of the monotonic stack.

Notice that all the remaining elements in the stack are popped out of the stack in lines 14-21. From PROPERTY 1 - Next Smaller Element(2) we could know that these elements do not have their next greater elements.

---

1019. Next Greater Node In Linked List

[1019. Next Greater Node In Linked List]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
      auto idx = 0;
      struct IdxVal {
        int idx;
        int val;
      };
      auto s = std::vector<IdxVal>{};
      auto result = std::vector<int>{};
      while(head) {
        const auto val = head->val;
        const auto curIdx = idx;
        while(!s.empty() && s.back().val < val) {
          const auto poppedIdx = s.back().idx;
          if(!(poppedIdx < result.size())) {
            result.resize(poppedIdx + 1);
          }
          result[poppedIdx] = val;
          s.pop_back();
        }
        s.push_back(IdxVal{curIdx, val});
        ++idx;
        head = head->next;
      }
      
      while(!s.empty()) {
        const auto poppedIdx = s.back().idx;
        if(!(poppedIdx < result.size())) {
            result.resize(poppedIdx + 1);
        }
        result[poppedIdx] = 0;
        s.pop_back();
      }
      
      return result;
    }
};

This problem builds the monotonic stack from a linked-list. Monotonic does not require random access to elements in the container. Thus it could be used as an online algorithm.

---

739. Daily Temperatures

This problem gives you an array of temperatures. You are asked to find the distance between every element and its next greater element.

[739. Daily Temperatures]

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temps) {
      auto result = std::vector<int>(temps.size(), 0);
      auto s = std::vector<int>{};
      for(auto i = 0; i < temps.size(); ++i) {
        const auto temp = temps[i];
        while(!s.empty() && temps[s.back()] < temp) {
          result[s.back()] = i - s.back();
          s.pop_back();
        }
        s.push_back(i);
      }
      return result;
    }
};

---

1475. Final Prices With a Special Discount in a Shop

This problem asks you to find the next not greater element instead of the next smaller element. In the line 8 of the code, we should use prices[s.back()] >= price instead of prices[s.back()] > price.

[1475. Final Prices With a Special Discount in a Shop]

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
      auto s = std::vector<size_t>{};
      auto result = prices;
      for(size_t i = 0; i < prices.size(); ++i) {
        const auto price = prices[i];
        while(!s.empty() && prices[s.back()] >= price) {
          result[s.back()] = prices[s.back()] - price;
          s.pop_back();
        }
        s.push_back(i);
      }
      return result;
    }
};

---

1762. Buildings With an Ocean View

Find the elements that do not have the next greater element. Use PROPERTY 1 - Next Greater (Smaller) Element(2), just return the final stack.

[1762. Buildings With an Ocean View]

class Solution {
public:
    vector<int> findBuildings(vector<int>& heights) {
      auto s = std::vector<int>{};
      for(auto i = 0; i < heights.size(); ++i) {
        const auto height = heights[i];
        while(!s.empty() && heights[s.back()] <= height) {
          s.pop_back();
        }
        s.push_back(i);
      }
      return s;
    }
};

Previous Not Greater (Not Smaller) Element

901. Online Stock Span

This problem asks for an online algorithm to find the previous greater element.

From PROPERTY 2 - Previous Not Greater Element we could know that if we pop the stack whenever the top of the stack is smaller than the current one when the current one is pushed into the stack, the previous element in the stack is the previous not smaller element. Not smaller means greater or equal to.

However, if we only want the previous greater element, we have to pop the stack whenever the top of the stack is smaller than or equal to the current one (line 7 prices_[s_.back()] <= prices_[idx] in the code).

[901. Online Stock Span]

class StockSpanner {
public:  
    int next(int price) {
      const int idx = prices_.size();
      prices_.push_back(price);
      
      while(!s_.empty() && prices_[s_.back()] <= prices_[idx]) {
        s_.pop_back();
      }
      auto first = s_.empty() ? 0 : s_.back() + 1;
      s_.push_back(idx);
      return idx - first + 1;
    }
private:
  std::vector<int> s_ = {};
  std::vector<int> prices_{};
};

Subarrays for an Element being Minimum/Maximum

2334. Subarray With Elements Greater Than Varying Threshold

The problem asks you to find any subarray s such that every element in the subarray is greater than threshold / len(s), where threshold is a given number and len(s) is the length of the subarray.

Every element in the subarray is greater than threshold / len(s) is equivalent to the minimum of the subarray s is greater than threshold / len(s).

Denote the set of all subarrays of A as {s}. {s} could be divided into len(A) disjoint subsets {s_i}, 0 <= i < len(A). the subset of subarrays {s_i} has the property such that A[i] is the minimum element and is the first minimum element in the subarray.

In each subset {s_i}, there exists an element in the subset {s_i}, the subarray sl_i, such that sl_i is the longest subarray in the subset {s_i}.

Because all the subarrays in the subset {s_i} shares the same minimum A[i]. If the longest one of them has A[i] > threshold / len(sl_i) hold true, then all of them have A[i] > threshold / len.

Thus for each subarray in the subset {s_i}, we need only to check the longest one of them.

From PROPERTY 3 - Minimum in Subarray we know that monotonic stack could find out the longest subarray R_i for each element i as the first minimum of that subarray. when i is popped out of the stack. Using PROPERTY 3, we could find the longest subarray with A[i] as the first minimum — sl_i for each i. Then we just check if sl_i has A[i] > threshold / len(sl_i).

[2334. Subarray With Elements Greater Than Varying Threshold]

class Solution {
public:
  int validSubarraySize(vector<int>& nums, int threshold) {
    auto s = std::vector<int>{};    
    for(int i = 0; i < nums.size(); ++i) {
      while(!s.empty() && nums[i] <= nums[s.back()]) {
        const auto minIdx = s.back();
        s.pop_back();
        const auto first = s.empty() ? 0 : s.back() + 1;
        const auto last = i;
        const auto minVal = nums[minIdx];
        const auto k = last - first;
        if(k * minVal > threshold) {
          return k;
        }
      }
      s.push_back(i);
    }
    
    while(!s.empty()) {
      const auto minIdx = s.back();
      s.pop_back();
      const auto first = s.empty() ? 0 : s.back() + 1;
      const auto last = nums.size();
      const auto minVal = nums[minIdx];
      const auto k = last - first;
      if(k * minVal > threshold) {
          return k;
      }
    }
    
    return -1;
  }
};

---

1944. Number of Visible People in a Queue

i could see j if i < j and all the element [i + 1, j) is smaller than A[i] and A[j].

That is to say, if j could be seen by i, then either A[i] is the maximum element in the subarray [i + 1, j) or i is the maximum element in the subarray [i + 1, j).

From PROPERTY 3 - Minimum in Subarray, with a monotonic decreasing stack, whenever an element i is popped out of the stack by another element j, A[i] is the first maximum in the subarray [i + 1, j). Thus j could be seen by i. When j is pushed into the stack, if the stack is not empty, let the top of the stack as h then A[h] > A[j], h is the maximum in the subarray [h, j]. Thus h could be seen by j.

class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
      auto result = std::vector<int>(heights.size(), 0);
      auto s = std::vector<int>{};
      
      for(int i = 0; i < heights.size(); ++i) {
        while(!s.empty() && heights[s.back()] < heights[i]) {
          ++result[s.back()];
          s.pop_back();
        }
        
        if(!s.empty()) {
          ++result[s.back()];
        }
        s.push_back(i);
      }
      
      return result;
    }
};

---

42. Trapping Rain Water

Warning: Solving this problem by monotonic stack is not a good idea.

Considering each bar in the elevation map, the volume of the water that being trapped on the bar trapVolume could be computed by:

• trapVolume = (rightBoundary - leftBoundary) * trapHeight
• rightBoundary - leftBoundary is the length of the subarray such that the bar being the first minimum in the subarray.
• trapHeight = min(height[leftBoundary], height[leftBoundary]) - midHeight.

For example, the water trapped on the bar with index 4 is computed in the following picture.

[42. Trapping Rain Water]

class Solution {
public:
    int trap(vector<int>& heights) {
      auto s = std::vector<int>{};
      auto result = 0;
      for(auto i = 0; i < heights.size(); ++i) {
        while(!s.empty() && heights[s.back()] < heights[i]) {
          const auto midHeight = heights[s.back()];
          s.pop_back();
          const auto leftBoundary = s.empty() ? 0 : s.back() + 1;
          const auto rightBoundary = i;
          const auto trapHeight = s.empty() ? 
            0 : std::min(heights[s.back()], heights[i]) - midHeight;
          const auto trapVolume = (rightBoundary - leftBoundary) * trapHeight;
          result += trapVolume;
        }
        s.push_back(i);
      }
      return result;
    }
};

---

84. Largest Rectangle in Histogram

For each bar b in the histogram, the area of the largest rectangle that includes the whole part of b could be computed by area = height[b] * len(s_b). s_b is the longest subarray such that b is the first minimum in the subarray.

[84. Largest Rectangle in Histogram]

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
      auto s = std::vector<int>{};
      auto res = 0;
      for(int i = 0; i < heights.size(); ++i) {
        while(!s.empty() && heights[s.back()] > heights[i]) {
          const int h = heights[s.back()];
          s.pop_back();
          const int first = s.empty() ? 0 : s.back() + 1;
          const int last = i;
          const int w = last - first;
          res = std::max(res, h * w);
        }
        s.push_back(i);
      }
      
      while(!s.empty()) {
        const int h = heights[s.back()];
        s.pop_back();
        const int first = s.empty() ? 0 : s.back() + 1;
        const int last = heights.size();
        const int w = last - first;
        res = std::max(res, h * w);
      }
      
      return res;
    }
};

---

1856. Maximum Subarray Min-Product

This problem asks you to find out the largest min-product of all its subarrays. Min-product of an array is the minimum of the array times the sum of the array.

All the numbers in the array are greater than zero. Thus if the minimum of the subarray does not change, the longer the subarray is, the larger the min-product will be.

Denote the set of all subarrays of A as {s}. {s} could be divided into len(A) disjoint subsets {s_i}, 0 <= i < len(A). the subset {s_i} has the property such that A[i] is the minimum element and is the first minimum element in the subarray.

For each subset {s_i}, there exists a subarray sl_i such that sl_i is the longest subarray in the subset{s_i}. All the elements in the subset {s_i} share the same minimum A[i]. Therefore, sl_i must have the largest min-product among all the subarrays in the subset {s_i}.

The problem is then solved by finding the largest sl_i of all subsets {s_i}.

[1856. Maximum Subarray Min-Product]

auto PrefixSum(const vector<int>& nums) {
  auto prefixSum = std::vector<int64_t>{};
  prefixSum.push_back(0);
  for(auto num : nums) {
    prefixSum.push_back(prefixSum.back() + num);
  }
  return prefixSum;
}

static constexpr const int M = 1e9 + 7;

class Solution {
public:
    int maxSumMinProduct(vector<int>& nums) {
      auto prefixSum = PrefixSum(nums);
      auto SubarraySum = [&prefixSum](auto first, auto last){
        return prefixSum[last] - prefixSum[first];
      };
      
      auto s = std::vector<int64_t>{};
      int64_t result = 0; 
      
      for(auto i = 0; i <= nums.size(); ++i) {
        while(!s.empty() 
              && (i == nums.size() 
                  || nums[s.back()] > nums[i])) {
          const int64_t curNum = nums[s.back()];
          s.pop_back();
          const auto first = s.empty() ? 0 : s.back() + 1;
          const auto last  = i;
          const auto subarraySum = SubarraySum(first, last);
          const auto minProduct = curNum * subarraySum;
          result = std::max(result, minProduct);
        }
        s.push_back(i);
      }
      
      return result % M;
    }
};

---

Number of such subarrays

From PROPERTY 3 - Minimum(Maximum) in Subarray we could derive the longest subarray for every element i as the first minimum of the subarray. We could also find the set {s_i} such that all the subarray in this set shares the same first minimum element A[i]. But can we find how many subarrays the set {s_i} has?

Denote sl_i = [a, b); a <= i < b to be the longest subarray for element i as the first minimum element. a and b could be determined when the element i is popped out of the stack as described in PROPERTY 3 - Minimum(Maximum) in Subarray.

Then, the number of subarrays in {s_i} is (i - a + 1) * (b - i)
The number of subarrays that end with i is (i - a + 1).
The number of subarrays that start with i is (b - i).

---

1063. Number of Valid Subarrays

This problem asks for the number of non-empty subarrays with the leftmost element of the subarray not larger than other elements in the subarray.

From PROPERTY 3 - Minimum(Maximum) in Subarray we could derive the longest subarray sl_i = [a, b); a <= i < b for every element i as the first minimum of the subarray. For each element i, all the subarrays that contain i, with the leftmost element of the subarrays not larger than other elements in the subarrays, a subset of {s_i} mentioned previously. The number of such subarrays is n_i = (b_i - i). Compute n_i for each i and adds them together.

[1063. Number of Valid Subarrays]

class Solution {
public:
    int validSubarrays(vector<int>& nums) {
      auto s = std::vector<int>{};
      auto result = 0;
      for(auto i = 0; i <= nums.size(); ++i) {
        while(!s.empty() 
              && (i == nums.size() 
                  || nums[s.back()] > nums[i])) {
          result += i - s.back();
          s.pop_back();
        }
        s.push_back(i);
      }
      return result;
    }
};

---

907. Sum of Subarray Minimums

Find the sum of min(b), where b ranges over every subarray of arr.

This is equivalent to

- for each element in `A`, find the number of the subarrays such that `A[i]` is the first minimum. Then sum all such numbers.

[907. Sum of Subarray Minimums]

static constexpr const int M = 1e9 + 7;

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
      auto s = std::vector<int>{};
      const int len = arr.size();
      auto computeRangeSum = [&arr](int first, int mid, int last){
        const auto left  = mid - first + 1;
        // count[mid + 1, last - 1] + 1 --> last - 1 - mid - 1 + 1 + 1 --> last - mid
        const auto right = last - mid;
        return (left * right * arr[mid]) % M;
      };
      
      auto result = 0;
      for(auto i = 0; i < len; ++i) {
        const auto curVal = arr[i];
        while(!s.empty() && arr[s.back()] > curVal) {
          const auto mid = s.back();
          s.pop_back();
          const auto first = s.empty() ? 0 : s.back() + 1;
          const auto last  = i;
          const auto sum = computeRangeSum(first, mid, last) % M;
          result = result % M + sum;
        }
        s.push_back(i);
      }
      
      while(!s.empty()) {
        const auto mid = s.back();
        s.pop_back();
        const auto first = s.empty() ? 0 : s.back() + 1;
        const auto last = len;
        const auto sum = computeRangeSum(first, mid, last);
        result = result % M + sum;
      }
      return result;
    }
};

---

Stack-sortable Permutation, 231 Pattern

If a permutation could be sorted using a monotonic (increasing) stack, then this permutation is called stack-sortable permutation. It is proved that Stack-sortable permutations are equivalent to the permutations that do not contain the permutation pattern 231.

456. 132 Pattern

This problem asks you to check if the input array contains 132 permutation pattern. 132 is the reverse of 231 pattern. We could simply reverse the input array and check if the reversed array is stack-sortable using a monotonic increasing stack.

[456. 132 Pattern]

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
      std::reverse(nums.begin(), nums.end());
      auto s = std::vector<int>{};
      auto output = std::vector<int>{};
      for(auto n : nums) {
        while(!s.empty() && n > s.back()) {
          output.push_back(s.back());
          s.pop_back();
        }
        s.push_back(n);
      }
      while(!s.empty()) {
        output.push_back(s.back());
        s.pop_back();
      }
      return !std::is_sorted(output.begin(), output.end());
    }
};

---

Lexicorgraphically Smallest Subsequence After Removing K Elements

You are given a string s and an integer k. Return the lexicographically smallest subsequence of s after removing at most k letters.

There exists a greedy strategy using a monotonic increasing stack for this problem. Run monotonic increasing stack algorithm with the following constraints:

• When trying to pop an element from the stack
  • If k > 0, decrease k, and pop the element from the stack.
  • Otherwise, keep the element in the stack.
• After all the letters in the string have been pushed into the stack, if we still have k > 0:
  • Pop the top element from the stack. Decrease k for each popped element. Do this until k == 0.
• Return the stack as the result.

---

402. Remove K Digits

This problem gives you a string of digits. It asks you to remove exactly k digits of the string. The integer represented by the result should be the smallest possible one.

The number represented by a digit string is smallest when the digit string is lexicographically smallest. We could apply the previously mentioned greedy strategy to this problem. There is no difference between removing at most k and removing exactly k digits. The more you remove, the lexicographically smaller the result will be.

Notice that the digits remaining in the stack could start with '0', you need to remove these zeros.

[402. Remove K Digits]

template<typename It>
auto RemoveKDigits(It first, It last, int k) {
  auto s = std::vector<typename It::value_type>{};
  for(auto it = first; it < last; ++it) {
    while(!s.empty() 
          && s.back() > *it
          && k > 0) {
      s.pop_back();
      --k;
    }
    s.push_back(*it);
  }
  
  while(k > 0) {
    s.pop_back();
    --k;
  }
  
  auto numberRangeFirst = s.begin();
  while(numberRangeFirst < s.end() && *numberRangeFirst == '0') {
    ++numberRangeFirst;
  }
  if(!(numberRangeFirst < s.end())) {
    return "0"s;
  }
  auto result = std::string{};
  std::copy(numberRangeFirst, s.end(), std::back_inserter(result));
  return result;
}

class Solution {
public:
    string removeKdigits(string num, int k) {
      return RemoveKDigits(num.begin(), num.end(), k);    
    }
};

---

316. Remove Duplicate Letters
1081. Smallest Subsequence of Distinct Characters

Leetcode 1081 and Leetcode 316 are the same.

In this problem, you are asked to return a lexicographically smallest subsequence such that every letter in the original string appears once and only once.

The greedy strategy could still be applied to this problem with adjustment.

• Compute the frequency freq[c] of each letter c in the string. (line 5 - 10, line 29, 35)
• Once a letter c is in the stack, no more letter c should be pushed into the stack. (line 21 - 24)
• If there is only one letter c (freq[c] == 1), the letter c should not be popped out of the stack. (line 28)

[316. Remove Duplicate Letters]

int CharToIndex(char c) {
  return c - 'a';
}

std::array<int, 26> FreqCount(const std::string& str) {
  auto result = std::array<int, 26>{};
  for(auto c : str) {
    ++result[CharToIndex(c)];
  }
  return result;
}

class Solution {
public:
    string removeDuplicateLetters(string s) {
      auto letterInStack = std::array<int, 26>{};
      auto result = std::string{};
      auto freq = FreqCount(s);
      
      for(auto c : s) {
        if(letterInStack[CharToIndex(c)]) {
          --freq[CharToIndex(c)];
          continue;
        }
        
        while(!result.empty() 
              && result.back() > c 
              && freq[CharToIndex(result.back())] > 1) {
          letterInStack[CharToIndex(result.back())] = 0;
          --freq[CharToIndex(result.back())];
          result.pop_back();
        }
        
        result.push_back(c);
        letterInStack[CharToIndex(c)] = 1;
      }
      
      return result;
    }
};

---

2030. Smallest K-Length Subsequence With Occurrences of a Letter

This problem is similar with 316. Remove Duplicate Letters but with more contraints.

class Solution {
public:
    string smallestSubsequence(const std::string& s, int k, char letter, int repetition) {
      auto letterChances = std::count(s.begin(), s.end(), letter) - repetition;
      auto needRemove = s.size() - k;
      
      auto res = std::string{};
      auto i = 0;
      for(char c : s) {        
        while(!res.empty() 
              && res.back() > c
             && needRemove) {
          if(res.back() == letter && letterChances) {
            --letterChances;
            --needRemove;
            res.pop_back();
          } else if (res.back() != letter){
            --needRemove;
            res.pop_back();
          } else {
            break;
          }
        }
        res.push_back(c);
      }
      
      auto removeIdxs = std::unordered_set<int>{};
      for(int i = res.size() - 1; i >= 0 && needRemove; --i) {
        if(res[i] == letter && letterChances) {
          --letterChances;
          --needRemove;
          removeIdxs.insert(i);
        } else if (res[i] != letter){
          --needRemove;
          removeIdxs.insert(i);
        }
      }
      
      auto r = std::string{};
      for(int i = 0; i < res.size(); ++i) {
        if(removeIdxs.count(i)) {
          continue;
        }
        r.push_back(res[i]);
      }
      
      return r;
    }
};