Stack

tags: String,LeetCode101,Stack,Hash Table,Hash Set I have solved this problem years before, LeetCode: 316.Remove Duplicate Letters, but still stuck on it. The key idea is not only about stack, but also required a map to record how many same letters behind current one. Which helps us to decide if drop current letter or not, when the new letter is less than the top of stack, which means smaller in lexicographical order....

tags: String,LeetCode101,Hash Set,Hash Table,Stack The key idea is similar to LeetCode101: 316. Remove Duplicate Letters, we use a HashMap to track how many letters which is same in the string. Then we use a HashSet to store appeared letters. When there is no more letters appeared in the HashSet, it’s time to partition. class Solution { public: vector<int> partitionLabels(string s) { unordered_map<char, int> cntOfLetters; unordered_set<char> appearedLetters; vector<int> r; int count = 0; for (auto iter = s....

tags: Tricky,Stack,LeetCode101,Integer Overflow The key is how to detect integer overflow without store to a larger size integer. For this purpose, we could detect integer overflow before carry: The maximal of INT_MAX before carry is \(\frac{INT\_MAX}{10}\). We continue compare pop with the suffix of INT_MAX, 7, if maximal before carry is equal to \(\frac{INT\_MAX}{10}\). The minimal of INT_MIN before carry is \(\frac{INT\_MIN}{10}\) too. We continue compare pop with the suffix of INT_MIN, -8, if minimal before carry is equal to \(\frac{INT\_MIN}{10}\)....

tags: Stack Intuition for (int i = 0; i < pushed.size(); i++) { if (pushed[i] != popped[pushed.size() - 1 - i]) { return false; } } But the pop/push operations can happend in any sequence. Stack Using a stack. Returns false, IF the next value neither the popped nor pushed. In each sequence we must do a operation: push or pop. When to push: stack is empty, or top of stack is not current popped value When to pop:...

tags: Stack,LeetCode101 Stack class Solution { public: string minRemoveToMakeValid(string s) { stack<char> st; char open = '(', close = ')'; int open_count = 0; string res; // forward to remove unnecessary close parentheses for (auto iter = s.begin(); iter != s.end(); ++iter) { if (*iter == open) { open_count++; } if (open_count == 0 && *iter == close) { continue; } if (*iter == close) { open_count--; } st.push(*iter); } int close_count = 0; // backward to remove unnecessary open parentheses while (!...

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 (!...

tags: Linked List,Stack, LeetCode101,2. Add Two Numbers 两数之和的进阶版，位高的数字在链表的头部，常规解法是通过「栈」进行反转链表，然后回退到2. Add Two Numbers的解法。