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 (!st.empty()) { if (st.top() == close) { close_count++; } if (st.top() == open) { if (close_count == 0 ) { st.pop(); continue; } close_count--; } res.push_back(st.top()); st.pop(); } reverse(res.begin(), res.end()); return res; } };
tags: Tricky,LeetCode101 original: 0, 2, 1, 4, 3, 5, 7, 6 max: 0, 2, 2, 4, 4, 5, 7, 7 sorted: 0, 1, 2, 3, 4, 5, 6, 7 index: 0, 1, 2, 3, 4, 5, 6, 7 As shown above, the position of break point is same to the position of max value of chunks. So here: ...
tags: Algorithm
tags: Monotonic Stack,LeetCode101,LeetCode101: 496. Next Greater Element I Mono-descreasing stack class Solution { public: vector<int> dailyTemperatures(vector<int>& temperatures) { vector<int> res(temperatures.size(), 0); stack<int> st; for (int i = 0; i < temperatures.size(); i++) { while (!st.empty() && temperatures[st.top()] < temperatures[i]) { res[st.top()] = i - st.top(); st.pop(); } st.push(i); } return res; } }; [73,74,75,71,69,72,76,73]