??個人主頁：@小羊 ??所屬專欄：LeetCode 熱題 100 很榮幸您能閱讀我的文章，誠請評論指點，歡迎歡迎 ~

---

棧

有效的括號

• 有效的括號

class Solution {
public:bool isValid(string s) {stack<char> st;for (char e : s){if (st.empty()) st.push(e);else if (st.top() == '(' && e == ')' || st.top() == '{' && e == '}'|| st.top() == '[' && e == ']') st.pop();else st.push(e);}return st.empty();}
};

---

最小棧

• 最小棧

class MinStack {stack<int> st;stack<int> minst;
public:MinStack() {}void push(int val) {st.push(val);if (minst.empty() || val <= minst.top()){minst.push(val);}}void pop() {if (st.top() == minst.top()){minst.pop();}st.pop();}int top() {return st.top();}int getMin() {return minst.top();}
};

---

字符串解碼

• 字符串解碼

class Solution {
public:string decodeString(string s) {int i = 0;return dfs(s, i);}string dfs(const string& s, int& i){string str;while (i < s.size() && s[i] != ']'){if (isdigit(s[i])){int num = 0;while (i < s.size() && s[i] != '['){num = num * 10 + s[i++] - '0';}i++; // 跳過'['string tmp = dfs(s, i);i++; // 跳過']'while (num--) str += tmp;}else str += s[i++];}return str;}
};

---

每日溫度

• 每日溫度

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();stack<int> st;vector<int> res(n);for (int i = 0; i < n; i++){while (st.size() && temperatures[st.top()] < temperatures[i]){int t = st.top();st.pop();res[t] = i - t;}st.push(i);}return res;}
};

---

柱狀圖中最大的矩形

• 柱狀圖中最大的矩形

1. 單調遞增棧：分別從左向右和從右向左遍歷，找到每個柱子左邊和右邊第一個比它矮的柱子位置。
2. 計算寬度：對于每個柱子，其左右邊界之間的距離即為矩形的寬度，高度為當前柱子的高度。
3. 求最大值：遍歷所有可能的矩形，找出面積最大的一個。

單調棧。

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int n = heights.size();vector<int> left(n), right(n);stack<int> st;for (int i = 0; i < n; i++){while (st.size() && heights[st.top()] >= heights[i]){st.pop();}left[i] = st.empty() ? -1 : st.top();st.push(i);}st = stack<int>();for (int i = n - 1; i >= 0; i--){while (st.size() && heights[st.top()] >= heights[i]){st.pop();}right[i] = st.empty() ? n : st.top();st.push(i);}int res = 0;for (int i = 0; i < n; i++){res = max(res, (right[i] - left[i] - 1) * heights[i]);}return res;}
};

優化。

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int n = heights.size();vector<int> left(n, -1), right(n, n);stack<int> st;for (int i = 0; i < n; i++){while (st.size() && heights[st.top()] > heights[i]){right[st.top()] = i;st.pop();}if (st.size()) left[i] = st.top(); st.push(i);}int res = 0;for (int i = 0; i < n; i++){res = max(res, (right[i] - left[i] - 1) * heights[i]);}return res;}
};

---

堆

數組中的第K個最大元素

• 數組中的第K個最大元素

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {int n = nums.size();for (int i = n - 2 / 2; i >= 0; i--){adjust_down(nums, i, n);}while (--k){swap(nums[0], nums[--n]);adjust_down(nums, 0, n);}return nums[0];}void adjust_down(vector<int>& nums, int parent, int n){int child = 2 * parent + 1;while (child < n) {if (child + 1 < n && nums[child + 1] > nums[child]) child++;if (nums[child] > nums[parent]){swap(nums[child], nums[parent]);parent = child;child = 2 * parent + 1;}else break;}}
};

---

---

---

---

本篇文章的分享就到這里了，如果您覺得在本文有所收獲，還請留下您的三連支持哦~