Notes

tags: Monotonic Stack,LeetCode101,Binary Search Tree Mono-descreasing stack Key: The largest number is the root, that we can observe in by iteration. We must clear the stack to fill the right side of BST after loop. The last popped element is the left of current node. From top to bottom, the top element is the right side of the element that under the top. class Solution { public: TreeNode* constructMaximumBinaryTree(vector<int>& nums) { vector<TreeNode*> res(nums.size(), nullptr); stack<int> st; // mono-descreasing stack, remove smaller elements before pushing. TreeNode* root = nullptr; for (int i = 0;i < nums.size(); i++) { res[i] = new TreeNode(nums[i]); while (!st.empty() && nums[st.top()] < nums[i]) { int j = st.top(); st.pop(); if (!st.empty() && nums[st.top()] < nums[i]) { res[st.top()]->right = res[j]; } else { res[i]->left = res[j]; } } if (root == nullptr || res[i]->val > root->val) { root = res[i]; } st.push(i); } while (st.size() > 1) { int j = st.top(); st.pop(); res[st.top()]->right = res[j]; } return root; } };

tags: Monotonic Stack,LeetCode101 Mono-increasing stack Key: Some case should move backward as the new value we meeted is larger than it. When we meet 2 in the stack, and here we need move backward. Some case we need move forward, as the following values are the mono-increaing stack: [1, 2, 5, 3, 4] class Solution { public: int findUnsortedSubarray(vector<int>& nums) { stack<int> st; // mono-increasing int left = -1, right = -2; for (int i = 0; i < nums.size(); i++) { while (!st.empty() && nums[st.top()] > nums[i]) { // move backward if (left == -1 || st.top() < left) { left = st.top(); // left should be the previous index } // move forward for (int j = i; j < nums.size() && nums[j] < nums[st.top()]; j++) { if (j > right) { right = j; } } st.pop(); } st.push(i); } return (right - left) + 1; } }; Failed test cases [2,6,4,8,10,9,15] [1, 2, 3, 4] [1] [2,1] [1,3,2,2,2] [1,2,3,3,3] [2,3,3,2,4] [1,2,5,3,4] [1,3,5,2,4]

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’. ...