Notes

tags: Monotonic Stack,LeetCode101 related: LeetCode101: 496. Next Greater Element I Mono-descreasing stack / normal order loop twice Loop twice to solve circular interger array Mono-descreasing stack to store index, avoid HashMap in Next Greater Element I, as there is a cicular array. class Solution { public: vector<int> nextGreaterElements(vector<int>& nums) { vector<int> res(nums.size(), -1); stack<int> st; for (int j = 0, i = 0; j < nums.size() * 2; ++j) { i = j >= nums.size() ? j - nums.size() : j; while (!st.empty() && nums[st.top()] < nums[i]) { res[st.top()] = nums[i]; st.pop(); } st.push(i); } return res; } };

tags: Monotonic Stack,Hash Table,LeetCode101 Mono-descreasing and reverse order travel class Solution { public: vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { // Mono-descreasing and reverse order travel. // The next greater of the popped value is the top of the stack, if it has any. // // For example: [1,3,4,2] // the stack goes: // [2] // [4] -> 2 // [4, 3, 1] stack<int> st; vector<int> res; unordered_map<int, int> m; for (int i = nums2.size() - 1; i >= 0; i--) { while (!st.empty() && st.top() < nums2[i]) { int c = st.top(); st.pop(); if (!st.empty()) { m[c] = st.top(); } } st.push(nums2[i]); } while (st.size() > 1) { int c = st.top(); st.pop(); m[c] = st.top(); } for (int i = 0; i < nums1.size(); i++) { if (m.find(nums1[i]) != m.end()) { res.push_back(m[nums1[i]]); } else { res.push_back(-1); } } return res; } }; /* [1,3,5,2,4] [6,5,4,3,2,1,7] The stack goes: [7, 1] [7, 2] -> 1 and 1 is next greater is the top of the stack */

tags: Monotonic Stack,LeetCode101 Mono-increasing stack and reverse order travel (Not Work) Notes: We attempt to remove the most large numbers in the left, first, we use the right n numbers to meet the requirements, which is num.length - k and then, using a monotonic increasing stack to keep the result as samller as we can. (A monotonic increasing stack will remove larger elements before pushing.) Also note that: the result’s length is not actually equal num.length - k, it’s less than or equal num.length - k, like num = “10200”, k = 1. Which means the result in stack could be longer than the required or leading ‘0’. ...

tags: Monotonic Stack,LeetCode101,Tricky We travel the numbers in the reverse order: Use a mono-increasing stack to find the largest number(3 in the 132 pattern), the value popped from stack is the second large number(2 in the 132 pattern), if any value less than the second large number, returns true. // Note: // // - subsequence is not contiguous, is i < j < k, not i + 1 = j, j + 1 = k // class Solution { public: bool find132pattern(vector<int>& nums) { int K = INT_MIN; stack<int> mst; // mono-increasing stack for (int i = nums.size() - 1; i >= 0; i--) { if (nums[i] < K) { return true; } while (!mst.empty() && mst.top() < nums[i]) { K = mst.top(); mst.pop(); } mst.push(nums[i]); } return false; } };

tags: Data Structures,Stack source: “Monotonic Stack.” Accessed March 13, 2022. https://liuzhenglaichn.gitbook.io/algorithm/monotonic-stack. A monotonic stack is a stack whose elements are monotonically increasing or descreasing. It’s not only about the order in the stack, it’s also about remove larger/smaller elements before pushing. Monotonically descreasing we need to pop smaller elements from the stack before pushing a new element: vector<int> nums; // fill nums stack<int> st; for (auto i = nums.size() - 1; i >= 0; i--) { while (!st.empty() && st.top() > nums[i]) { st.pop(); } st.push(nums[i]) } To push 3 to [5, 4, 2, 1], we need pop 2, 1 out first. Then the stack become [5, 4, 3] Monotonically increasing vice versa. ...