Read Again
- Partition Equal Subset Sum
bool canPartition(vector<int>& nums) {
int ttl_sum = std::accumulate(nums.begin(), nums.end(), 0);
if (ttl_sum & 1) return false;
ttl_sum = ttl_sum >> 1;
vector<bool> record(ttl_sum+1, false);
record[0] = true;
for (const auto& num : nums) {
for (int cur = ttl_sum; cur >= num; --cur) {
record[cur] = record[cur] || record[cur-num];
if (record[ttl_sum]) return true;
}
}
return false;
}
// 85. Maximal Rectangle
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
vector<int> heights(matrix[0].size() + 2, 0);
int max_area = 0;
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[0].size(); ++j) {
if (matrix[i][j] == '0') {
heights[j+1] = 0;
} else {
++heights[j+1];
}
}
max_area = max(max_area, MaxHistogramArea(heights));
}
return max_area;
}
int MaxHistogramArea(const vector<int>& heights) {
stack<int> record;
record.push(heights[0]);
int max_area = 0;
for (int i = 1; i < heights.size(); ++i) {
while (heights[record.top()] > heights[i]) {
const int mid = record.top();
record.pop();
max_area = max(max_area, heights[mid] * (i - record.top() - 1));
}
record.push(i);
}
return max_area;
}
// 53. Maximum Subarray
int maxSubArray(vector<int>& nums) {
int max_res = nums[0];
int ttl_sum = nums[0];
for (int i = 1; i < nums.size(); ++i) {
ttl_sum = max(nums[i], ttl_sum+nums[i]);
max_res = max(ttl_sum, max_res);
}
return max_res;
}```
- Task Scheduler
```c++
// 621. Task Scheduler
int leastInterval(vector<char>& tasks, int n) {
unordered_map<char, int> record;
for (const auto task : tasks) {
++record[task];
}
priority_queue<int> status;
for (const auto [name, frequency] : record) {
status.push(frequency);
}
int ans = 0;
while (!status.empty()) {
vector<int> tmp;
int count = 0;
for (int i = 0; i <= n; ++i) {
if (status.empty()) break;
tmp.push_back(status.top());
++count;
status.pop();
}
for (auto& t : tmp) {
if (--t > 0) {
status.push(t);
}
}
ans += status.empty() ? count : n + 1;
}
return ans;
}
// 57. Insert Interval
vector<vector<int>> insert(vector<vector<int>>& intervals,
vector<int>& new_interval) {
auto lower_it = lower_bound(begin(intervals), end(intervals),
new_interval, [](const vector<int>& p1, const vector<int>& p2) {
return p1[1] < p2[0];
});
auto upper_it = upper_bound(begin(intervals), end(intervals),
new_interval, [](const vector<int>& p1, const vector<int>& p2) {
return p1[1] < p2[0];
});
if (lower_it == upper_it) {
intervals.insert(lower_it, new_interval);
}
else {
--upper_it;
lower_it->at(0) = min(lower_it->at(0), new_interval[0]);
lower_it->at(1) = max(upper_it->at(1), new_interval[1]);
++lower_it;
++upper_it;
intervals.erase(lower_it, upper_it);
}
return intervals;
}
// 127. Word Ladder
bool CanTransform(const string& s1, const string& s2) {
if (s1.size() != s2.size()) return false;
int count = 0;
for (int i = 0; i < s1.size(); ++i)
if (s1[i] != s2[i]) ++count;
return count == 1;
}
int ladderLength(string begin_word, string end_word, vector<string>& word_list) {
unordered_map<string, vector<string>> record;
word_list.emplace_back(begin_word);
for (int i = 0; i < word_list.size(); ++i) {
for (int j = i + 1; j < word_list.size(); ++j) {
if (CanTransform(word_list[i], word_list[j])) {
record[word_list[i]].emplace_back(word_list[j]);
record[word_list[j]].emplace_back(word_list[i]);
}
}
}
int transform_length = 1;
unordered_set<string> visited;
unordered_set<string> cur_visited;
cur_visited.insert(begin_word);
while (!cur_visited.empty()) {
++transform_length;
unordered_set<string> new_visited;
for (const auto& cur : cur_visited) {
visited.insert(cur);
for (const auto& word : record[cur]) {
if (visited.count(word) <= 0) {
new_visited.insert(word);
}
if (word == end_word) return transform_length;
}
}
cur_visited = new_visited;
}
return 0;
}
// 79. Word Search
// Note: variable should be set out of the function
vector<int> dir_x = {0, 1, 0, - 1};
vector<int> dir_y = {-1, 0, 1, 0};
bool Exist(const vector<vector<char>>& board, const int row, const int col,
const int idx, const string& word, vector<vector<bool>>& record) {
if (idx >= word.size()) return true;
if (col < 0 || row < 0 || col >= board[0].size() || row >= board.size() ||
(word[idx] != board[row][col]))
return false;
if (record[row][col]) return false;
record[row][col] = true;
for (int i = 0; i < 4; ++i) {
const int x = dir_x[i] + col;
const int y = dir_y[i] + row;
if (Exist(board, y, x, idx+1, word, record)) {
return true;
}
}
record[row][col] = false;
return false;
}
bool exist(vector<vector<char>>& board, string word) {
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[0].size(); ++j) {
vector<vector<bool>> record(board.size(), vector<bool>(board[0].size(), false));
if (Exist(board, i, j, 0, word, record)) return true;
}
}
return false;
}
- Largest Rectangle in Histogram
// 84. Largest Rectangle in Histogram
int largestRectangleArea(vector<int>& heights) {
heights.insert(heights.begin(), 0);
heights.emplace_back(0);
stack<int> his;
his.push(0);
int max_area = 0;
for (int i = 1; i < heights.size(); ++i) {
while (heights[his.top()] > heights[i]) {
const int tp = his.top();
his.pop();
const int stt = his.top();
max_area = max(max_area, heights[tp] * (i - stt - 1));
}
his.push(i);
}
return max_area;
}
// Method II
int largestRectangleArea(vector<int>& heights) {
if (heights.empty()) return 0;
vector<int> left_index(heights.size(), 0);
vector<int> right_index(heights.size(), 0);
left_index[0] = -1;
right_index[heights.size()-1] = heights.size();
for (int i = 1; i < heights.size(); ++i) {
int t = i - 1;
while (t >= 0 && heights[t] >= heights[i]) t = left_index[t];
left_index[i] = t;
}
for (int i = heights.size() - 1; i >= 0; --i) {
int t = i + 1;
while (t < heights.size() && heights[t] >= heights[i])
t = right_index[t];
right_index[i] = t;
}
int max_area = 0;
for (int i = 0; i < heights.size(); ++i) {
max_area = max(max_area, heights[i] * (right_index[i] - left_index[i] - 1));
}
return max_area;
}
// 76. Minimum Window Substring
string minWindow(string s, string t) {
unordered_map<char, int> record;
unordered_set<char> dict;
for (const auto& c : t) {
dict.insert(c);
--record[c];
}
string res;
int stt_idx = 0;
int diff = dict.size();
for (int fast = 0, slow = 0; fast < s.size(); ++fast) {
if (dict.count(s[fast]) > 0) {
++record[s[fast]];
if (!record[s[fast]]) --diff;
}
while (dict.count(s[slow]) <= 0 ||
(dict.count(s[slow]) > 0 && record[s[slow]] > 0)) {
if (dict.count(s[slow]) > 0) {
--record[s[slow]];
if (record[s[slow]] == -1) ++diff;
}
++slow;
if (slow >= s.size()) break;
}
if (!diff) {
res = fast - slow + 1 < res.size() || res.empty()?
s.substr(slow, fast - slow + 1) : res;
}
}
return res;
}
- Longest Palindromic Substring
// 5. Longest Palindromic Substring
string longestPalindrome(string s) {
vector<vector<bool>> record(s.size(), vector<bool>(s.size(), false));
string res;
for (int i = 0; i < s.size(); ++i) {
record[i][i] = true;
res = s.substr(i, 1);
if (i != s.size() - 1) record[i+1][i] = true;
}
for (int i = 0; i < s.size(); ++i) {
for (int j = i - 1; j >= 0; --j) {
if (s[j] == s[i] && record[j+1][i-1]) {
record[j][i] = true;
if (i - j + 1 > res.size())
res = s.substr(j, i - j + 1);
}
}
}
return res;
}
// 152. Maximum Product Subarray
int maxProduct(vector<int>& nums) {
int max_cur = nums[0];
int min_cur = nums[0];
int res = nums[0];
for (int i = 1; i < nums.size(); ++i) {
if (!nums[i]) {
max_cur = min_cur = 0;
}
else {
const int num1 = nums[i]*max_cur;
const int num2 = nums[i]*min_cur;
max_cur = max(max(num1, num2), nums[i]);
min_cur = min(min(num1, num2), nums[i]);
}
res = max(res, max_cur);
}
return res;
}
- Container With Most Water
// 11. Container With Most Water
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int max_area = 0;
while (left < right) {
max_area = max((right - left) * min(height[left],
height[right]), max_area);
if (height[left] < height[right]) ++left;
else --right;
}
return max_area;
}
// 139. Word Break
bool wordBreak(string s, vector<string>& dict) {
unordered_set<string> dict_set(dict.begin(), dict.end());
unordered_set<int> lens;
for (const auto& w : dict_set) {
lens.insert(w.size());
}
vector<bool> record(s.size() + 1, false);
int idx = 0;
record[0] = true;
while (idx < s.size()) {
if (!record[idx]) {
++idx;
continue;
}
for (const auto& len : lens) {
if (dict_set.find(s.substr(idx, len)) != dict_set.end())
record[idx + len] = true;
}
++idx;
}
return record[s.size()];
}
- Search in Rotated Sorted Array
// 33. Search in Rotated Sorted Array
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left + 1 < right) {
int mid = (right - left)/2 + left;
if (nums[left] < nums[mid]) {
if (nums[left] <= target && nums[mid] >= target) right = mid;
else left = mid;
} else {
if (nums[mid] <= target && nums[right] >= target) left = mid;
else right = mid;
}
}
if (nums[left] == target) return left;
if (nums[right] == target) return right;
return -1;
}
- Product of Array Except Self
// 238. Product of Array Except Self
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> left(nums.size(), 1);
vector<int> right(nums.size(), 1);
for (int i = 1; i < nums.size(); ++i) {
left[i] = left[i-1] * nums[i-1];
}
for (int i = nums.size() - 2; i >= 0; --i) {
right[i] = right[i+1] * nums[i+1];
}
for (int i = 0; i < nums.size(); ++i) {
left[i] *= right[i];
}
return left;
}
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> right(nums.size(), 1);
int cur = 1;
for (int i = nums.size() - 2; i >= 0; --i) {
right[i] = right[i+1] * nums[i+1];
}
for (int i = 0; i < nums.size(); ++i) {
right[i] *= cur;
cur *= nums[i];
}
return right;
}
// 15. 3Sum
vector<vector<int>> threeSum(vector<int>& nums) {
sort(begin(nums), end(nums));
unordered_map<int, int> index;
for (int i = 0; i < nums.size(); ++i) {
index[nums[i]] = i;
}
vector<vector<int>> ans;
int prev = INT_MAX;
for (int i = 0; i < nums.size(); ++i) {
while (i < nums.size() && nums[i] == prev) ++i;
if (i + 1 >= nums.size()) break;
prev = nums[i];
int prev2 = INT_MAX;
for (int j = i + 1; j < nums.size(); ++j) {
if (prev2 == nums[j]) continue;
prev2 = nums[j];
int target = -(nums[i] + nums[j]);
if (index.count(target) > 0 && index[target] > j) {
ans.push_back({nums[i], nums[j], nums[index[target]]});
}
}
}
return ans;
}
NOT Important
Finish without block
// 78. Subsets
vector<vector<int>> sub_sets_;
void SubsetInternal(const vector<int>& nums, const int idx,
vector<int> cur) {
if (idx >= nums.size()) {
sub_sets_.push_back(cur);
return;
}
SubsetInternal(nums, idx+1, cur);
cur.push_back(nums[idx]);
SubsetInternal(nums, idx+1, cur);
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> cur;
SubsetInternal(nums, 0, cur);
return sub_sets_;
}
// 310. Minimum Height Trees
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if (n < 2) return {0};
vector<int> ans;
unordered_map<int, unordered_set<int>> graph;
for (const auto& edge : edges) {
graph[edge[0]].insert(edge[1]);
graph[edge[1]].insert(edge[0]);
}
for (const auto& [v, node] : graph) {
if (node.size() == 1)
ans.push_back(v);
}
while (!ans.empty()) {
unordered_set<int> next;
for (const auto& v : ans) {
if (graph[v].size() > 0) {
const int num = *(graph[v].begin());
graph[num].erase(v);
if (graph[num].size() == 1)
next.insert(num);
}
graph.erase(v);
}
if (next.empty()) return ans;
ans = vector<int>(begin(next), end(next));
}
return {};
}
// 146. LRU Cache
class LRUCache {
public:
LRUCache(int capacity): cap_(capacity) {}
int get(int key) {
if (data_.find(key) == data_.end()) return -1;
const auto val_and_it = data_[key];
keys_.push_front(key);
keys_.erase(val_and_it.second);
data_[key] = make_pair(val_and_it.first, keys_.begin());
return val_and_it.first;
}
void put(int key, int value) {
if (data_.count(key) > 0) {
const auto val_and_it = data_[key];
keys_.erase(val_and_it.second);
}
keys_.push_front(key);
data_[key] = make_pair(value, keys_.begin());
if (cap_ < keys_.size()) {
const int val = keys_.back();
auto it = keys_.end();
--it;
keys_.erase(it);
data_.erase(val);
}
}
private:
int cap_ = 0;
unordered_map<int, pair<int, list<int>::iterator>> data_;
list<int> keys_;
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
- Kth Smallest Element in a BST
// 230. Kth Smallest Element in a BST
int count_ = 0;
int kthSmallest(TreeNode* root, int k) {
if (!root) return -1;
const int left = kthSmallest(root->left, k);
if (left >= 0) return left;
++count_;
if (k == count_) return root->val;
return kthSmallest(root->right, k);
}
// 1. Two Sum
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> remain;
for (int i = 0; i < nums.size(); ++i) {
if (remain.find(target - nums[i]) != remain.end()) {
return {remain[target-nums[i]], i};
}
remain[nums[i]] = i;
}
return {};
}
- Best Time to Buy and Sell Stock
// 121. Best Time to Buy and Sell Stock
int maxProfit(vector<int>& prices) {
int min_price = prices[0];
int profit = 0;
for (int i = 1; i < prices.size(); ++i) {
profit = max(profit, prices[i] - min_price);
min_price = min(prices[i], min_price);
}
return profit;
}
// 217. Contains Duplicate
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> record;
for (const auto& num:nums) {
const auto it = record.insert(num);
if (!it.second) return true;
}
return false;
}
// 20. Valid Parentheses
bool isValid(string s) {
stack<char> stk;
unordered_map<char, char> mp{ { ']', '['}, {')', '('},
{'}', '{'} };
for (const auto& c : s) {
if (mp.find(c) != mp.end()) {
if (stk.empty() || stk.top() != mp[c]) {
return false;
}
stk.pop();
} else {
stk.push(c);
}
}
return stk.empty();
}
// 21. Merge Two Sorted Lists
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* head = new ListNode(0);
ListNode* cur = head;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val <= l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if (l1 != nullptr) cur->next = l1;
if (l2 != nullptr) cur->next = l2;
return head->next;
}
// 125. Valid Palindrome
bool IsQualify(const char c) {
return (c >= 'a' && c <= 'z') ||
(c >= 'A' && c <= 'Z') ||
(c >= '0' && c <= '9');
}
bool Same(const char a, const char b) {
if (isdigit(a) || isdigit(b)) {
return a == b;
}
return (a == b) || (a + 'A' - 'a' == b) ||
(a + 'a' == b + 'A');
}
bool isPalindrome(string s) {
int left = 0;
int right = s.size() - 1;
while (left < right) {
if (!IsQualify(s[left])) {
++left;
continue;
}
if (!IsQualify(s[right])) {
--right;
continue;
}
if (!Same(s[left++], s[right--])) {
return false;
}
}
return true;
}
// 226. Invert Binary Tree
TreeNode* invertTree(TreeNode* root) {
if (!root) return nullptr;
TreeNode* tmp = root->left;
root->left = invertTree(root->right);
root->right = invertTree(tmp);
return root;
}
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
vector<int> record(26, 0);
for (int i = 0; i < s.size(); ++i) {
++record[s[i]-'a'];
--record[t[i]-'a'];
}
for (int i = 0; i < 26; ++i) {
if (record[i]) return false;
}
return true;
}
// 704. Binary Search
int search(vector<int>& nums, int target) {
int stt = 0;
int fin = nums.size() - 1;
while (stt + 1 < fin) {
int mid = stt + (fin - stt)/2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) stt = mid;
else fin = mid;
}
if (nums[stt] == target) return stt;
if (nums[fin] == target) return fin;
return -1;
}
// 733. Flood Fill
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
queue<pair<int, int>> cur;
int init = image[sr][sc];
if (init != color) {
cur.push({sr, sc});
image[sr][sc] = color;
}
vector<int> dir_r({-1, 0, 1, 0});
vector<int> dir_c({0, 1, 0, -1});
while (!cur.empty()) {
const auto tp = cur.front();
cur.pop();
for (int i = 0; i < 4; ++i) {
const auto r = tp.first + dir_r[i];
const auto c = tp.second + dir_c[i];
if (r < 0 || r >= image.size() || c < 0 || c >= image[0].size())
continue;
if (image[r][c] == init) {
image[r][c] = color;
cur.push({r, c});
}
}
}
return image;
}
- Lowest Common Ancestor of a Binary Search Tree
// 235. Lowest Common Ancestor of a Binary Search Tree
TreeNode* lowestCommonAncestor(TreeNode* root,
TreeNode* p, TreeNode* q) {
if (!root) return nullptr;
if (p == root || q == root) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != nullptr && right != nullptr) {
return root;
}
if (left != nullptr) return left;
if (right != nullptr) return right;
return nullptr;
}
// 141. Linked List Cycle
bool hasCycle(ListNode *head) {
if (!head) return false;
ListNode* fast = head;
ListNode* slow = head->next;
while (fast && slow) {
if (fast == slow) return true;
fast = fast->next;
if (slow->next == nullptr) break;
slow = slow->next->next;
}
return false;
}
// 110. Balanced Binary Tree
int IsBalanced(TreeNode* root) {
if (root == nullptr) return 0;
int left = IsBalanced(root->left);
int right = IsBalanced(root->right);
if (left > 5000 || right > 5000) return INT_MAX;
if (abs(left-right) > 1) return INT_MAX;
return max(left, right) + 1;
}
bool isBalanced(TreeNode* root) {
return IsBalanced(root) <= 5000;
}
// 278. First Bad Version
int firstBadVersion(int n) {
int stt = 1;
int fin = n;
while (stt + 1 < fin) {
int mid = (fin - stt)/2 + stt;
if (isBadVersion(mid)) fin = mid;
else stt = mid;
}
return isBadVersion(stt)?stt:fin;
}
// 383. Ransom Note
bool canConstruct(string ransomNote, string magazine) {
int len = 26;
vector<int> record(len, 0);
for (const auto& c : magazine) {
++record[c - 'a'];
}
for (const auto& c : ransomNote) {
--record[c - 'a'];
}
for (int i = 0; i < len; ++i) {
if (record[i] < 0) return false;
}
return true;
}
// 70. Climbing Stairs
int climbStairs(int n) {
if (n <= 2) return n;
int s1 = 1;
int s2 = 2;
for (int i = 3; i <= n; ++i) {
int tmp = s2;
s2 += s1;
s1 = tmp;
}
return s2;
}
- Reversed Linked List
// 206. Reverse Linked List
ListNode* reverseList(ListNode* head) {
ListNode* cur = head;
ListNode* prev = nullptr;
while (cur != nullptr) {
ListNode* tmp = cur->next;
cur->next = prev;
prev = cur;
cur = tmp;
}
return prev;
}
- Add Binary
string addBinary(string a, string b) {
string c;
int len_a = size(a) - 1;
int len_b = size(b) - 1;
int rem = 0;
while (len_a >= 0 || len_b >= 0) {
int s = (len_a >= 0?(a[len_a] - '0'):0) +
(len_b >= 0?(b[len_b] - '0'):0) + rem;
c = to_string(s%2) + c;
rem = s/2;
--len_a;
--len_b;
}
if (rem) c = to_string(rem) + c;
return c;
}
- Middle of the Linked List
// 876. Middle of the Linked List
ListNode* middleNode(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast != nullptr && slow != nullptr) {
fast = fast->next;
if (fast != nullptr) fast = fast->next;
else break;
slow = slow->next;
}
return slow;
}
- Maximum Depth of Binary Tree
// 104. Maximum Depth of Binary Tree
int maxDepth(TreeNode* root) {
if (!root) return 0;
return max(maxDepth(root->left),
maxDepth(root->right)) + 1;
}
// 217. Contains Duplicate
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> record;
for (const auto& num : nums) {
const auto it = record.insert(num);
if (!it.second) return true;
}
return false;
}
// 169. Majority Element
int majorityElement(vector<int>& nums) {
int target = INT_MIN;
int pair = 0;
for (int i = 0; i < nums.size()-1; i += 2) {
if (nums[i] == nums[i+1]) {
if (target != nums[i]) {
if (!pair) {
++pair;
target = nums[i];
} else {
--pair;
}
if (!pair) target = INT_MAX;
} else {
++pair;
}
}
}
return pair > 0? target : nums[nums.size()-1];
}
// 543. Diameter of Binary Tree
// Return pair(max_depth, max_diameter)
pair<int, int> GetDiameter(TreeNode* root) {
if (!root) return {0, 0};
const auto left = GetDiameter(root->left);
const auto right = GetDiameter(root->right);
return {max(left.first, right.first) + 1,
max(max(left.second, right.second),
left.first + right.first + 1
)};
}
int diameterOfBinaryTree(TreeNode* root) {
return GetDiameter(root).second - 1;
}
// 542. 01 Matrix
vector<int> dir_r{-1, 0, 1, 0};
vector<int> dir_c{0, 1, 0, -1};
bool HasZero(const int row, const int col,
const vector<vector<int>>& mat) {
for (int i = 0; i < 4; ++i) {
const auto r = dir_r[i] + row;
const auto c = dir_c[i] + col;
if (r >= 0 && r < mat.size() && c >= 0 &&
c < mat[0].size() && !mat[r][c])
return true;
}
return false;
}
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
queue<pair<int, int>> record;
for (int i = 0; i < mat.size(); ++i) {
for (int j = 0; j < mat[0].size(); ++j) {
if (mat[i][j] && HasZero(i, j, mat)) {
record.push({i, j});
++mat[i][j];
}
}
}
while (!record.empty()) {
const auto [r, c] = record.front();
record.pop();
const auto& cur = mat[r][c];
for (int i = 0; i < 4; ++i) {
const auto new_r = dir_r[i] + r;
const auto new_c = dir_c[i] + c;
if (new_r >= 0 && new_r < mat.size() &&
new_c >= 0 && new_c < mat[0].size()
&& mat[new_r][new_c] == 1) {
mat[new_r][new_c] = cur + 1;
record.push({new_r, new_c});
}
}
}
for (int i = 0; i < mat.size(); ++i) {
for (int j = 0; j < mat[0].size(); ++j) {
if (mat[i][j]) --mat[i][j];
}
}
return mat;
}
- Binary Tree Level Order Traversal
// 102. Binary Tree Level Order Traversal
void LevelOrder(TreeNode* root, const int level,
vector<vector<int>>* ans) {
if (!root) return;
if (ans->size() <= level) ans->push_back({});
(*ans)[level].emplace_back(root->val);
LevelOrder(root->left, level+1, ans);
LevelOrder(root->right, level+1, ans);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
LevelOrder(root, 0, &ans);
return ans;
}
- Longest Substring Without Repeating Characters
int lengthOfLongestSubstring(string s) {
int max_len = 0;
unordered_map<int, int> record;
for (int i = 0, j = 0; i < s.size(); ++i) {
++record[s[i]];
while (record[s[i]] > 1) {
--record[s[j]];
++j;
}
max_len = max(max_len, i - j + 1);
}
return max_len;
}
// 133. Clone Graph
unordered_map<Node*, Node*> record;
Node* cloneGraph(Node* node) {
if (!node) return nullptr;
if (record.find(node) != record.end())
return record[node];
Node* copy = new Node(node->val);
record[node] = copy;
for (const auto& n : node->neighbors) {
const auto new_n = cloneGraph(n);
if (!new_n) continue;
copy->neighbors.emplace_back(new_n);
}
return copy;
}
- K Closest Points to Origin
// 973. K Closest Points to Origin
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
vector<vector<int>> ans;
const auto comp = [&](const pair<int, int>& p1, const pair<int, int>& p2) {
const int dis1 = p1.first*p1.first + p1.second*p1.second;
const int dis2 = p2.first*p2.first + p2.second*p2.second;
return dis1 < dis2;
};
priority_queue<pair<int, int>, vector<pair<int, int>>,
decltype(comp)> pq(comp);
for (const auto& pt : points) {
pq.push({pt[0], pt[1]});
if (pq.size() > K) pq.pop();
}
while (!pq.empty()) {
const auto tp = pq.top();
pq.pop();
ans.push_back({tp.first, tp.second});
}
return ans;
}
- Implement Queue using Stacks
// 232. Implement Queue using Stacks
class MyQueue {
public:
/** Initialize your data structure here. */
MyQueue() {
stk_ = vector<stack<int>>(2);
}
/** Push element x to the back of queue. */
void push(int x) {
stk_[0].push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
if (stk_[1].empty()) {
while (!stk_[0].empty()) {
stk_[1].push(stk_[0].top());
stk_[0].pop();
}
}
const int res = stk_[1].top();
stk_[1].pop();
return res;
}
/** Get the front element. */
int peek() {
if (stk_[1].empty()) {
while (!stk_[0].empty()) {
stk_[1].push(stk_[0].top());
stk_[0].pop();
}
}
return stk_[1].top();
}
/** Returns whether the queue is empty. */
bool empty() {
return stk_[0].empty() && stk_[1].empty();
}
private:
vector<stack<int>> stk_;
};
bool Search(const int idx, const unordered_map<int, vector<int>>& graph,
vector<int>& visited) {
if (visited[idx] == 2) return true;
if (visited[idx] == 1) return false;
visited[idx] = 1;
if (graph.find(idx) != graph.end()) {
for (const auto& node : graph.at(idx)) {
if (!Search(node, graph, visited))
return false;
}
}
visited[idx] = 2;
return true;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> visited(numCourses, 0);
unordered_map<int, vector<int>> graph;
for (const auto& prerequisite : prerequisites) {
graph[prerequisite[1]].emplace_back(prerequisite[0]);
}
for (int i = 0; i < numCourses; ++i) {
if (visited[i]) continue;
if (!Search(i, graph, visited)) return false;
}
return true;
}
- Implement Trie (Prefix Tree)
// 208. Implement Trie (Prefix Tree)
struct Node {
bool is_end = false;
Node* children[26] = {nullptr};
};
Node* parent_ = nullptr;
/** Initialize your data structure here. */
Trie() {
parent_ = new Node();
}
/** Inserts a word into the trie. */
void insert(string word) {
Node* cur = parent_;
for (const auto& c : word) {
if (!cur->children[c-'a'])
cur->children[c-'a'] = new Node();
cur = cur->children[c-'a'];
}
cur->is_end = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
Node* cur = parent_;
for (const auto& c : word) {
if (!cur->children[c-'a'])
return false;
cur = cur->children[c-'a'];
}
return cur != nullptr && cur->is_end;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
Node* cur = parent_;
for (const auto& c : prefix) {
if (!cur->children[c-'a'])
return false;
cur = cur->children[c-'a'];
}
return cur != nullptr;
}
- Validate Binary Search Tree
// 98. Validate Binary Search Tree
bool isValidBST(TreeNode* root,
double left = -DBL_MAX,
double right = DBL_MAX) {
if (!root) return true;
if (root->val <= left || root->val >= right)
return false;
return isValidBST(root->left, left, root->val) &&
isValidBST(root->right, root->val, right);
}
// 200. Number of Islands
int numIslands(vector<vector<char>>& grid) {
int mark = 0;
vector<int> dir_x({0, 1, 0, -1});
vector<int> dir_y({-1, 0, 1, 0});
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == '1') {
++mark;
grid[i][j] = '0';
queue<pair<int, int>> record;
record.push({i, j});
while (!record.empty()) {
cout << record.size() << endl;
const auto tp = record.front();
record.pop();
for (int k = 0; k < 4; ++k) {
const auto x = dir_x[k] + tp.second;
const auto y = dir_y[k] + tp.first;
if (x < 0 || y < 0 || y >= grid.size() ||
x >= grid[0].size() || grid[y][x] != '1')
continue;
grid[y][x] = '0';
record.push({y, x});
}
}
}
}
}
return mark;
}
int coinChange(vector<int>& coins, int amount) {
vector<int> record(amount+1, INT_MAX);
record[0] = 0;
for (int i = 0; i <= amount; ++i) {
for (const auto& coin : coins) {
if (i - coin >= 0 && record[i-coin]!= INT_MAX) {
record[i] = min(record[i], record[i-coin]+1);
}
}
}
return record[amount] == INT_MAX? -1:record[amount];
}
// 155. Min Stack
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {}
void push(int x) {
stk_.push(x);
if (min_stk_.empty() || min_stk_.top() >= x) {
min_stk_.push(x);
}
}
void pop() {
const int tp = top();
const int min_tp = getMin();
stk_.pop();
if (min_tp == tp) min_stk_.pop();
}
int top() {
return stk_.top();
}
int getMin() {
return min_stk_.top();
}
private:
stack<int> min_stk_;
stack<int> stk_;
};
// 221. Maximal Square
int maximalSquare(vector<vector<char>>& matrix) {
vector<vector<int>> record(matrix.size()+1,
vector<int>(matrix[0].size()+1, 0));
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[0].size(); ++j) {
record[i+1][j+1] = (matrix[i][j]-'0') + record[i+1][j];
}
}
for (int j = 0; j < matrix[0].size(); ++j) {
for (int i = 0; i < matrix.size(); ++i) {
record[i+1][j+1] += record[i][j+1];
}
}
int max_size = min(matrix.size(), matrix[0].size());
for (int size = max_size; size > 0; --size) {
for (int i = size; i < record.size(); ++i) {
for (int j = size; j < record[0].size(); ++j) {
if (record[i][j] + record[i-size][j-size]
- record[i-size][j] - record[i][j-size] == size*size)
return size * size;
}
}
}
return 0;
}
// 994. Rotting Oranges
int orangesRotting(vector<vector<int>>& grid) {
int min_num = 0;
int cnt_fresh = 0;
queue<pair<int, int>> record;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == 2) {
record.push({i, j});
} else if (grid[i][j] == 1) {
++cnt_fresh;
}
}
}
const vector<int> dir_x = {0, 1, 0, -1};
const vector<int> dir_y = {-1, 0, 1, 0};
while (!record.empty()) {
const int size = record.size();
for (int i = 0; i < size; ++i) {
const auto tp = record.front();
record.pop();
for (int j = 0; j < 4; ++j) {
const int x = dir_x[j] + tp.second;
const int y = dir_y[j] + tp.first;
if (x < 0 || y < 0 || x >= grid[0].size() ||
y >= grid.size() || grid[y][x] != 1)
continue;
grid[y][x] = 2;
record.push({y, x});
--cnt_fresh;
}
}
if (record.empty()) break;
++min_num;
}
return !cnt_fresh?min_num:-1;
}
// 75. Sort Colors
void sortColors(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
while (!nums[left] && left < right) ++left;
while (nums[right] && left < right) --right;
if (left < right) swap(nums[left], nums[right]);
}
right = nums.size() - 1;
while (left < right) {
while (nums[left] == 1 && left < right) ++left;
while (nums[right] == 2 && left < right) --right;
if (left < right) swap(nums[left], nums[right]);
}
}
- Lowest Common Ancestor of a Binary Tree
// 236. Lowest Common Ancestor of a Binary Tree
TreeNode* lowestCommonAncestor(TreeNode* root,
TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
return left && right? root: (left?left:right);
}
// 56. Merge Intervals
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> ans;
sort(begin(intervals), end(intervals));
int stt = intervals[0][0];
int fin = intervals[0][1];
for (const auto& inter:intervals) {
if (inter[0] <= fin) {
fin = max(inter[1], fin);
} else {
ans.push_back({stt, fin});
stt = inter[0];
fin = inter[1];
}
}
ans.push_back({stt, fin});
return ans;
}
// 8. String to Integer (atoi)
const long long max_num = INT_MAX;
const long long min_num = INT_MIN;
int myAtoi(string s) {
int lead_status = 0;
long long res = 0;
for (const auto& c : s) {
if (isdigit(c)) {
res = res * 10 + c - '0';
if (lead_status != -1) lead_status = 1;
if (lead_status * res <= min_num) return min_num;
if (lead_status * res >= max_num) return max_num;
} else if (c == ' ') {
if (lead_status) return res * lead_status;
} else if (c == '-' || c == '+') {
if (lead_status) return res * lead_status;
if (c == '-') lead_status = -1;
if (c == '+') lead_status = 1;
} else {
return res * lead_status;
}
}
return res * lead_status;
}
// 39. Combination Sum
vector<vector<int>> ans_;
void GetCombinationSum(const vector<int>& candidates, const int target,
const int cur_sum, const int idx, vector<int>& cur) {
if (cur_sum == target) {
ans_.push_back(cur);
return;
} else if (cur_sum > target) return;
for (int i = idx; i < candidates.size(); ++i) {
cur.push_back(candidates[i]);
GetCombinationSum(candidates, target, cur_sum + candidates[i], i, cur);
cur.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> cur;
int cur_sum = 0;
GetCombinationSum(candidates, target, cur_sum, 0, cur);
return ans_;
}
- Binary Tree Right Side View
// 199. Binary Tree Right Side View
vector<int> ans;
vector<int> rightSideView(TreeNode* root, int level = 0) {
if (!root) return {};
if (ans.size() <= level) ans.emplace_back(root->val);
rightSideView(root->right, level + 1);
rightSideView(root->left, level + 1);
return ans;
}
// 62. Unique Paths
int uniquePaths(int m, int n) {
vector<int> record(n, 1);
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
record[j] += record[j-1];
}
}
return record[n-1];
}
// 46. Permutations
void Permutation(const vector<int>& nums, vector<int> cur,
vector<bool>& visited, vector<vector<int>>& ans) {
if (cur.size() == nums.size()) {
ans.emplace_back(cur);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (!visited[i]) {
cur.push_back(nums[i]);
visited[i] = true;
Permutation(nums, cur, visited, ans);
cur.pop_back();
visited[i] = false;
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
vector<bool> visited(nums.size(), false);
vector<int> cur;
Permutation(nums, cur, visited, ans);
return ans;
}
// 54. Spiral Matrix
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> dir_x({1, 0, -1, 0});
vector<int> dir_y({0, 1, 0, -1});
vector<int> ans;
int cnt = 0;
int stt_x = -1, stt_y = 0;
while (true) {
const int new_x = stt_x + dir_x[cnt%4];
const int new_y = stt_y + dir_y[cnt%4];
if (new_x < 0 || new_x >= matrix[0].size() || new_y < 0 ||
new_y >= matrix.size() || matrix[new_y][new_x] == INT_MAX) {
++cnt;
continue;
}
stt_x = new_x;
stt_y = new_y;
ans.emplace_back(matrix[new_y][new_x]);
matrix[new_y][new_x] = INT_MAX;
if (ans.size() == matrix.size() * matrix[0].size()) break;
}
return ans;
}
- Time Based Key-Value Store
// 981. Time Based Key-Value Store
class TimeMap {
public:
/** Initialize your data structure here. */
TimeMap() {}
void set(string key, string value, int timestamp) {
data_[key].emplace_back(timestamp, value);
}
string get(string key, int timestamp) {
const auto& val_vec = data_.find(key);
if (val_vec == data_.end()) return "";
const auto cpm = [](const pair<int, string>& v1,
const pair<int, string>& v2) {
return v1.first < v2.first;
};
const vector<pair<int, string>>& data_vec = data_[key];
auto it = upper_bound(begin(data_vec), end(data_vec), make_pair(timestamp, ""), cpm);
if (it != data_vec.begin() && !data_vec.empty()) {
--it;
return it->second;
}
return "";
}
private:
unordered_map<string, vector<pair<int, string>>> data_;
};
// 409. Longest Palindrome
int longestPalindrome(string s) {
vector<int> record(256, 0);
for (const auto& c : s) ++record[c];
int sum = 0;
for (const auto& num: record) {
sum += num/2*2 + (num%2?
(!(sum%2)):0);
}
return sum;
}
- Construct Binary Tree from Preorder and Inorder Traversal
// 105. Construct Binary Tree from Preorder and Inorder Traversal
TreeNode* BuildTreeUtil(const vector<int>& preorder, const int s1, const int f1,
const vector<int>& inorder, const int s2, const int f2) {
if (s1 == f1) return new TreeNode(preorder[s1]);
if (s1 > f1) return nullptr;
const int split = inorder[s2];
int left = s1;
while (preorder[left] != split) ++left;
TreeNode* l_tree = BuildTreeUtil(preorder, s1, left - 1, inorder, s2 + 1, left - s1 + s2);
TreeNode* r_tree = BuildTreeUtil(preorder, left + 1, f1, inorder, f2 + left + 1 - f1, f2);
return new TreeNode(inorder[s2], l_tree, r_tree);
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return BuildTreeUtil(inorder, 0, preorder.size()-1,
preorder, 0, inorder.size()-1);
}
- Evaluate Reverse Polish Notation
// 150. Evaluate Reverse Polish Notation
bool IsOpe(const std::string& token) {
if (token.size() > 1) return false;
return token[0] == '+' || token[0] == '-' ||
token[0] == '*' || token[0] == '/';
}
int evalRPN(vector<string>& tokens) {
stack<int> stk;
for (const auto& token : tokens) {
if (IsOpe(token)) {
const auto num1 = stk.top();
stk.pop();
const auto num2 = stk.top();
stk.pop();
const char ope = token[0];
switch (ope) {
case '+': stk.push(num1 + num2); break;
case '-': stk.push(num2 - num1); break;
case '/': stk.push(floor(num2/num1)); break;
case '*': stk.push(num1 * num2); break;
default: std::cout << "error\n";
}
} else {
const int num = stoi(token);
stk.push(num);
}
}
return stk.empty()?-1:stk.top();
}
// 721. Accounts Merge
int Find(const int root, vector<int>& parents) {
const int parent = parents[root];
if (parent != root) {
parents[root] = Find(parent, parents);
}
return parents[root];
}
void Union(const int left, const int right, vector<int>& parents,
vector<int>& ranks) {
const int left_parent = Find(left, parents);
const int right_parent = Find(right, parents);
if (ranks[left_parent] >= ranks[right_parent]) {
parents[right_parent] = left_parent;
if (ranks[left_parent] == ranks[right_parent])
++ranks[right_parent];
} else {
parents[left_parent] = right_parent;
}
}
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
unordered_map<string, string> email_to_name;
unordered_set<string> emails;
for (const auto& account : accounts) {
for (int i = 1; i < account.size(); ++i) {
email_to_name[account[i]] = account[0];
emails.insert(account[i]);
}
}
vector<string> emails_vec(emails.begin(), emails.end());
vector<int> emails_nums(emails_vec.size(), 0);
vector<int> ranks(emails_vec.size(), 0);
unordered_map<string, int> email_to_index;
for (int i = 0; i < emails_nums.size(); ++i) {
email_to_index[emails_vec[i]] = i;
emails_nums[i] = i;
}
for (const auto& account : accounts) {
for (int i = 1; i < account.size()-1; ++i) {
Union(email_to_index[account[i]], email_to_index[account[i+1]],
emails_nums, ranks);
}
}
unordered_map<int, set<int>> record;
for (int i = 0; i < emails_nums.size(); ++i) {
record[Find(i, emails_nums)].insert(i);
}
vector<vector<string>> ans;
for (const auto& [num, vec] : record) {
const string name = email_to_name[emails_vec[num]];
vector<string> vec_str;
for (const auto& v : vec) {
vec_str.emplace_back(emails_vec[v]);
}
sort(vec_str.begin(), vec_str.end());
ans.push_back(vec_str);
}
return ans;
}
- Find All Anagrams in a String
// 438. Find All Anagrams in a String
vector<int> findAnagrams(string s, string p) {
if (s.size() < p.size()) return {};
int num_zeros = 0;
vector<int> record(26, 0);
for (int i = 0; i < p.size(); ++i) {
++record[p[i]-'a'];
--record[s[i]-'a'];
}
for (const auto& num : record) {
if (num) ++num_zeros;
}
vector<int> res;
if (!num_zeros) res.emplace_back(0);
for (int i = p.size(); i < s.size(); ++i) {
--record[s[i]-'a'];
if (!record[s[i]-'a']) --num_zeros;
else if (record[s[i]-'a'] == -1) ++num_zeros;
++record[s[i-p.size()]-'a'];
if (record[s[i-p.size()]-'a'] == 1) ++num_zeros;
else if (!record[s[i-p.size()]-'a']) --num_zeros;
if (!num_zeros) res.emplace_back(i - p.size() + 1);
}
return res;
}
- Letter Combinations of a Phone Number
// 17. Letter Combinations of a Phone Number
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {};
unordered_map<char, vector<char>> table;
table['2'] = {'a', 'b', 'c'};
table['3'] = {'d', 'e', 'f'};
table['4'] = {'g', 'h', 'i'};
table['5'] = {'j', 'k', 'l'};
table['6'] = {'m', 'n', 'o'};
table['7'] = {'p', 'q', 'r', 's'};
table['8'] = {'t', 'u', 'v'};
table['9'] = {'w', 'x', 'y', 'z'};
queue<string> record;
record.push("");
int cur = 0;
while (!record.empty() && cur < digits.size()) {
const auto& vec = table[digits[cur]];
int size =record.size();
for (int i = 0; i < size; ++i) {
const auto str = record.front();
record.pop();
for (const auto& c : vec) {
record.push(str + c);
}
}
++cur;
}
vector<string> ans;
while (!record.empty()) {
ans.emplace_back(record.front());
record.pop();
}
return ans;
}
- Serialize and Deserialize Binary Tree
// 297. Serialize and Deserialize Binary Tree
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
queue<TreeNode*> tmp;
tmp.push(root);
string str;
while (!tmp.empty()) {
const auto node = tmp.front();
tmp.pop();
if (!node) {
str += ".;";
} else {
str += to_string(node->val) + ";";
tmp.push(node->left);
tmp.push(node->right);
}
}
return str;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
cout << data << endl;
TreeNode* root = nullptr;
queue<TreeNode*> tmp;
int prev = 0;
const auto it = data.find(';', prev + 1);
if (it == std::string::npos ||
data.substr(prev, it - prev) == ".") return root;
root = new TreeNode(stoi(data.substr(prev, it - prev)));
prev = it + 1;
tmp.push(root);
while (true) {
const auto it1 = data.find(';', prev + 1);
if (it1 == std::string::npos) break;
const std::string str1 = data.substr(prev, it1 - prev);
prev = it1 + 1;
auto tp = tmp.front();
tmp.pop();
if (str1 != ".") {
tp->left = new TreeNode(stoi(str1));
tmp.push(tp->left);
}
const auto it2 = data.find(';', prev + 1);
if (it2 == std::string::npos) break;
const std::string str2 = data.substr(prev, it2 - prev);
prev = it2 + 1;
if (str2 != ".") {
tp->right = new TreeNode(stoi(str2));
tmp.push(tp->right);
}
if (prev >= data.size()) break;
}
return root;
}
};
- Find Median from Data Stream
// 295. Find Median from Data Stream
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {}
void addNum(int num) {
cout << num << endl;
if (low_.empty() || low_.top() >= num) low_.push(num);
else high_.push(num);
if (low_.size() + 1 < high_.size()) {
const int tp = high_.top();
high_.pop();
low_.push(tp);
} else if (high_.size() + 1 < low_.size()) {
const int tp = low_.top();
low_.pop();
high_.push(tp);
}
}
double findMedian() {
if (low_.size() > high_.size()) return low_.top();
else if (low_.size() < high_.size()) return high_.top();
else return (low_.top() + high_.top()) * 0.5;
}
private:
priority_queue<int> low_;
priority_queue<int, vector<int>, greater<int>> high_;
};
// 23. Merge k Sorted Lists
ListNode* MergeListsInternal(const vector<ListNode*>& lists,
const int stt, const int fin) {
if (stt > fin) return nullptr;
if (stt == fin) return lists[stt];
ListNode* left = MergeListsInternal(lists, stt, stt + (fin - stt)/2);
ListNode* right = MergeListsInternal(lists, stt + (fin - stt)/2 + 1, fin);
ListNode* root = new ListNode(0);
ListNode* cur = root;
while (left && right) {
if (left->val <= right->val) {
cur->next = left;
left = left->next;
} else {
cur->next = right;
right = right->next;
}
cur = cur->next;
}
if (left) cur->next = left;
if (right) cur->next = right;
return root->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
return MergeListsInternal(lists, 0, lists.size() - 1);
}
// 42. Trapping Rain Water
int trap(vector<int>& heights) {
stack<int> his;
int count = 0;
for (int i = 0; i < heights.size(); ++i) {
if (his.empty() || heights[his.top()] > heights[i]) {
his.push(i);
} else {
while (!his.empty() && heights[his.top()] <= heights[i]) {
const int mid = his.top();
his.pop();
if (his.empty()) break;
const int tp = his.top();
count += (min(heights[tp], heights[i]) - heights[mid]) *
(i - tp - 1);
}
his.push(i);
}
}
return count;
}
