栈和队列
解码字符串
class Solution {
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
public:
string decodeString(string s) {
string t = "";
stack<int> s_num;
stack<string> s_str;
int cnt = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] >= '0' && s[i] <= '9') {
cnt = 10 * cnt + s[i] - '0';
} else if (s[i] == '[') {
s_num.push(cnt);
s_str.push(t);
cnt = 0; t.clear();
} else if (s[i] == ']') {
int k = s_num.top(); s_num.pop();
for (int j = 0; j < k; ++j) s_str.top() += t;
t = s_str.top(); s_str.pop();
} else {
t += s[i];
}
}
return s_str.empty() ? t : s_str.top();
}
};
柱状图中最大的矩形
输入: [2,1,5,6,2,3]
输出: 10
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
image.png
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为
[2,1,5,6,2,3]
using namespace std;
int largestRectangleArea(vector<int>& heights) {
int res=0;
heights.push_back(0);
stack<int> st;
for(int i=0;i<heights.size();i++)
{
if(st.empty()||heights[i]>heights[st.top()])
{
st.push(i);
}
else
{
int curr=st.top();
st.pop();
int area=heights[curr]*(st.empty()?i:(i-1-st.top()));
cout<<area<<",";
res=max(res,area);
i--;
}
}
return res;
}
最大矩形
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6
解题思路：参考上一题，以求解某行为底的最大面积。用一个数组h来作为辅助数组.h[i]为这行的第i列往上有多少个连续的1,如果这行的i位置为0,则h[i]=0,否则h[i]=h[i]+1。
三角形最小路径和
动态规划
int minimumTotal(vector<vector<int>>& triangle) {
int row = triangle.size() - 1;
for (int i = row - 1; i >=0; i--)
{
int col = triangle[i].size();
for (int j = 0; j < col; j++)
{
triangle[row][j] = min(triangle[row][j], triangle[row][j+1]) + triangle[i][j];
}
}
return triangle[row][0];
}
去除重复字母
给定一个仅包含小写字母的字符串，去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
输入: "bcabc"
输出: "abc"
string removeDuplicateLetters(string s) {
int m[256] = {0}, visited[256] = {0};
string res = "0";
for (auto x : s) ++m[x];
for (auto x : s) {
--m[x];
if (visited[x]) continue;
while (x < res.back() && m[res.back()]) {
visited[res.back()] = 0;
res.pop_back();
}
res += x;
visited[x] = 1;
}
return res.substr(1);
}
简化路径
字符串处理，由于".."是返回上级目录（如果是根目录则不处理），因此可以考虑用栈记录路径名，以便于处理。需要注意几个细节：
重复连续出现的'/'，只按1个处理，即跳过重复连续出现的'/'；
如果路径名是"."，则不处理；
如果路径名是".."，则需要弹栈，如果栈为空，则不做处理；
如果路径名为其他字符串，入栈。
string simplifyPath(string path) {
string result, temp;
stringstream stringPath(path);
vector<string> v;
while (getline(stringPath, temp, '/'))
{
if (temp =="" || temp == ".") continue;
if (temp == ".." && !v.empty()) v.pop_back();
else if (temp != "..") v.push_back(temp);
}
for (auto eve : v) result += "/" + eve;
return result.empty() ? "/" : result;
}
滑动窗口最大值
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
注意：
你可以假设 k 总是有效的，1 ≤ k ≤ 输入数组的大小，且输入数组不为空。
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
deque<int> q;
for (int i = 0; i < nums.size(); ++i) {
if (!q.empty() && q.front() == i - k) q.pop_front();
while (!q.empty() && nums[q.back()] < nums[i]) q.pop_back();
q.push_back(i);
if (i >= k - 1) res.push_back(nums[q.front()]);
}
return res;
}
