这一类括号的题目,基本上都是左括号进栈,右括号判断终止;
class Solution {
public:
bool isValid(string s) {
stack <char> st;
st.push('#'); //可以不用判空
for (auto c : s){
if (c == '[' || c == '(' || c == '{'){
st.push(c);
}else if ((c == ')' && st.top() == '(') || (c == ']' && st.top() == '[') || (c == '}' && st.top() == '{')){
st.pop();
}else{
st.push(c);
}
}
if (st.size() == 1)return true;
return false;
}
};
这题跟上面的题目是一模一样的,最少添加就是有多少括号没有对象,,没有对象的括号都会留在栈中,有的都会出栈,所以就是求栈的大小;
class Solution {
public:
int minAddToMakeValid(string s) {
if (s.size() == 0)return 0;
stack <char> st;
st.push('#');
for (auto c : s){
if (c == '[' || c == '(' || c == '{'){
st.push(c);
}else if ((c == ')' && st.top() == '(') || (c == ']' && st.top() == '[') || (c == '}' && st.top() == '{')){
st.pop();
}else{
st.push(c);
}
}
return st.size() - 1;
}
};
这个题找最外层括号,直接上两例子:
(())=> (进栈, (进栈,)判断,(出栈, )判断,此时(出栈后栈大小为0,所以这括号就是最外层的括号,如果给这字符串编号:
也就是要把最外层括号里面的字符串截取出来:即截取:st.top() + 1 ~ i - 1;
class Solution {
public:
string removeOuterParentheses(string s) {
string result = "";
stack <int> st;
for (int i = 0; i < s.size(); i ++){
//判断栈的大小是不是0,来确定是不是最外层括号
if (s[i] == '(')st.push(i);
else if (s[i] == ')'){
if (st.size() == 1){
result += s.substr(st.top() + 1, i - 1 - st.top());
}
st.pop();
}
}
return result;
}
};
对于路径问题:首先通过分隔符/把各个字符串分开,然后一个一个讨论;
(1)//即:/与/之前是'',直接跳过即可
(2)/./即:/./之间是.,直接跳过即可
(3)/../即:如果是/home/../a,那么之后就为/a,然后/../前面没元素直接跳过即可;
class Solution {
public:
string simplifyPath(string path) {
stringstream is(path);
vector <string> vec;
string tmp, result = "/";
while (getline(is, tmp, '/')){
if (tmp == "." || tmp == "")continue;
else if (tmp == ".." && vec.size() != 0){
vec.pop_back();
}else if (tmp == ".." && vec.size() == 0){
continue;
}else{
vec.push_back(tmp);
}
}
for (int i = 0; i < vec.size(); i++){
if (i < vec.size() - 1){
result += vec[i] + "/";
}else{
result += vec[i];
}
}
return result;
}
};
不需多说
class Solution {
public:
stack <int> data;
int getNum(string str){
int sum = 0;
for (int i = 0; i < str.size(); i ++){
if (str[i] == '-')continue;
sum = sum * 10 - '0' + str[i];
}
if (str[0] == '-')return -sum;
return sum;
}
int calcu(int data1, string op, int data2){
if (op == "+")return data1 + data2;
if (op == "-")return data1 - data2;
if (op == "*")return data1 * data2;
if (op == "/")return data1 / data2;
return 0;
}
int evalRPN(vector<string>& tokens) {
int data1, data2;
string op;
for (auto c : tokens){
if (c == "+" || c == "-" || c == "*" || c == "/"){
data2 = data.top();
data.pop();
data1 = data.top();
data.pop();
data.push(calcu(data1, c, data2));
}else{
int num = getNum(c);
data.push(num);
}
}
return data.top();
}
};
class MinStack {
stack<int> x_stack;
stack<int> min_stack;
public:
MinStack() {
min_stack.push(INT_MAX);
}
void push(int x) {
x_stack.push(x);
min_stack.push(min(min_stack.top(), x));
}
void pop() {
x_stack.pop();
min_stack.pop();
}
int top() {
return x_stack.top();
}
int getMin() {
return min_stack.top();
}
};
通过栈保存当前符号类型即把题目看成一种累加:比如:-3+3 + 4 ==》 ans先加-3,再加3,再加4;右括号的话就把括号外面的符号进栈,如果括号外面是负号,那么括号里面负号就是正号,
class Solution {
public:
int calculate(string s) {
stack <int> st;
int sum = 0, op = 1, ans = 0;
st.push(op);
for (auto c : s){
if (c == ' ') continue;
else if (c >= '0'){
sum = sum * 10 - '0' + c;
}else{
ans += op * sum;
sum = 0;
if (c == '+')op = st.top();
if (c == '-')op = -st.top();
if (c == '(')st.push(op);
if (c == ')')st.pop();
}
}
return ans + op * sum;
}
};
队列实现栈:基本思路就是:一个队列存已经在队列中的,一个队列存新进入的数据,然后把先前的数据插入到新进入数据的后面
class MyStack {
private:
queue <int> que1;
queue <int> que2;
public:
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
que1.push(x);
while (!que2.empty()){
que1.push(que2.front());
que2.pop();
}
swap (que1, que2);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int num = que2.front();
que2.pop();
return num;
}
/** Get the top element. */
int top() {
return que2.front();
}
/** Returns whether the stack is empty. */
bool empty() {
return que2.empty();
}
};
用栈实现队列:一个栈输入,一个栈输出:插入数据进输入栈,如果输出数据,那就把输入栈的数据输出到输出栈,再从输出栈中输出,然后后续还需要输出数据,再从输出栈中查看,然后输出栈还有数据,那就直接出栈,否则,就把输入栈的数据输出到输出栈,再从输出栈中输出。
class MyQueue {
private:
stack<int> inStack, outStack;
void in2out() {
while (!inStack.empty()) {
outStack.push(inStack.top());
inStack.pop();
}
}
public:
MyQueue() {}
void push(int x) {
inStack.push(x);
}
int pop() {
if (outStack.empty()) {
in2out();
}
int x = outStack.top();
outStack.pop();
return x;
}
int peek() {
if (outStack.empty()) {
in2out();
}
return outStack.top();
}
bool empty() {
return inStack.empty() && outStack.empty();
}
};
验证这个序列是不是栈的出栈序列:这种题目的解法就是重现出栈场景,把数据一一入栈,在入栈的同时将其与给定的出栈序列比较,如果相同,那就把数据出栈,否则入栈,最后遍历完,如果栈为空,那就是出栈序列:
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack <int> st;
for (int i = 0; i < pushed.size(); i ++){
st.push(pushed[i]);
while (st.top() == popped[0]){
st.pop();
popped.erase(popped.begin(), ++popped.begin());
if (st.empty())break;
}
}
return st.empty();
}
};
class Solution {
public:
string removeDuplicates(string s) {
stack <char> st;
st.push('#');
for (auto c : s){
if (c == st.top()){
st.pop();
}else{
st.push(c);
}
}
string str = "";
while (st.top() != '#'){
str += st.top();
st.pop();
}
reverse(str.begin(), str.end());
return str;
}
};
通过[]入栈,来判断需要重复的字符,,通过栈内[之前的数字来决定次数:
class Solution {
public:
string decodeString(string s) {
stack <int> num;
stack <char> st;
string str = "", tmp;
int ans = 0;
for (auto c : s){
if (c >= '0' && c <= '9'){
ans = ans * 10 + c - '0';
}else if (c == ']'){
while (st.top() != '['){
tmp += st.top();
st.pop();
}
st.pop();
reverse(tmp.begin(), tmp.end());
for (int i = 0; i < num.top(); i ++){
str += tmp;
}
num.pop();
for (auto v : str){
st.push(v);
}
str = tmp = "";
}else if (c == '['){
num.push(ans);
ans = 0;
st.push(c);
}else{
st.push(c);
}
}
while (!st.empty()){
str += st.top();
st.pop();
}
reverse(str.begin(), str.end());
return str;
}
};
class Solution {
public:
int calPoints(vector<string>& ops) {
stack <int> st;
for (auto v : ops){
if (v == "D"){
st.push(st.top() * 2);
}else if (v == "C"){
st.pop();
}else if (v == "+"){
int data2 = st.top();
st.pop();
int data1 = st.top();
st.pop();
int data3 = data1 + data2;
st.push(data1);
st.push(data2);
st.push(data3);
}else{
int num = 0;
if (v[0] == '-'){
for (int i = 1; i < v.size(); i ++){
num = num * 10 + v[i] - '0';
}
st.push(-num);
}else{
for (int i = 0; i < v.size(); i ++){
num = num * 10 + v[i] - '0';
}
st.push(num);
}
}
}
int data = 0;
while (st.size() != 0){
data += st.top();
st.pop();
}
return data;
}
};
括号的分数:
(1)初始遇到(把0进栈;
(2)如果遇到)说明有完整的括号了,需要加分;
(3)怎么加分呢?若是栈顶为0,说明此时括号内无括号,栈顶的下一个表示前面并列的括号,也就是说,判断栈顶是否为0,0那么就加一,不是0,那么就在原有的基础是乘以2,之后再加上栈顶之后的;
class Solution {
public:
int scoreOfParentheses(string s) {
stack <int> st;
st.push(0);
for (auto c : s){
if (c == '('){
st.push(0);
}else{
int data1 = st.top();
st.pop();
int data2 = st.top();
st.pop();
st.push(max(1, 2 * data1) + data2);
}
}
return st.top();
}
};
class Solution {
public:
string decodeAtIndex(string S, int K) {
long long len = 0;
int N = S.size();
for (auto c : S){
if (isdigit(c)){
len *= c - '0';
}else{
len ++;
}
}
for (int i = N - 1; i >= 0; i --){
K %= len;
if (K == 0 && isalpha(S[i]))
return (string)"" + S[i];
if (isdigit(S[i])){
len /= S[i] - '0';
}else{
len --;
}
}
return "";
}
};
像这种用单调栈解法解答的题目有个特点:就是类似于山峰,或者山谷;比如1 2 3 4 8 6, 或者5 4 2 1 3;然后单调栈里一般存的是下标,这样更好的计算跨度。
对于这道题:2 1 5 6 2 3=》就是一种类似于山峰的:
(1)如果当前数比栈顶元素大,那么进栈,如果小,那就把栈顶元素出栈并且计算面积:
class Solution {
private:
stack <int> st;
public:
int largestRectangleArea(vector<int> &heights)
{
int ans = 0;
heights.insert(heights.begin(), 0);
heights.push_back(0);
st.push(0);
for (int i = 1; i < heights.size(); i ++){
while (heights[st.top()] > heights[i]){
int top = st.top();
st.pop();
int result = (i - st.top() - 1) * heights[top];
ans = max(ans, result);
}
st.push(i);
}
return ans;
}
};
题目都告诉你了:132模式,妥妥的山峰类型;但是这个加了一个条件就是山峰左边的数也要比右边小;
这个时候只要把左边的数或者右边的数记住,然后再进一个判断即可;
class Solution {
public:
//3 1 4 2;
bool find132pattern(vector<int>& nums) {
stack<int> st;
int n = nums.size(), k = INT_MIN;
for(int i = n - 1; i >= 0; i--){
if(nums[i] < k) return true;
while(!st.empty() and st.top() < nums[i]) {
k = max(k,st.top()); st.pop();
}
st.push(nums[i]);
}
return false;
}
};
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
vector <int> result;
int flag;
for (auto c : nums1){
flag = 0;
auto x = ::find(nums2.begin(), nums2.end(), c);
for (x + 1; x != nums2.end(); x ++){
if (*x > c){
flag = 1;
result.push_back(*x);
break;
}
}
if (flag == 0){
result.push_back(-1);
}
}
return result;
}
};
这是山谷类型:比如3 2 1 4 5 7 6;很明显3 2 1 的下一个更大是4,也就是如果栈为空,或者当前元素小于栈顶元素,那么直接入栈,如果大于栈顶元素,那就把对应下标对应的值改成当前元素:
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n=nums.size();
vector<int>res(n,-1);
stack<int>stk;
for (int i=0;i<n*2;i++)
{
while(!stk.empty()&&nums[i%n]>nums[stk.top()])
{
int j=stk.top();
stk.pop();
res[j]=nums[i%n];
}
stk.push(i%n);
}
return res;
}
};
无需多说,跟上面题目差不多;
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector <int> res(n, 0);
stack <int> st;
//[73, 74, 75, 71, 69, 72, 76, 73]
for (int i = 0; i < n; i ++){
while (!st.empty() && temperatures[i] > temperatures[st.top()]){
int cur = st.top();
st.pop();
res[cur] = i - cur;
}
st.push(i);
}
return res;
}
};
也是类似的,包括之后的;
class StockSpanner {
public:
StockSpanner() {
}
int next(int price) {
int count = 0;
while (!stk.empty() && price >= prices[stk.top()]) {
stk.pop();
}
count = stk.empty() ? prices.size() + 1 : prices.size() - stk.top();
prices.push_back(price);
stk.push(prices.size() - 1);
return count;
}
private:
vector<int> prices;
stack<int> stk;
};
对于这道题也是山谷类型: 4 5 6 3 7 8,3就是最小值,然后以他为最小值个数就是:3左边的数目加上3本身也就是m+1,类似的右边就是n + 1,总的个数就是3*(m + 1)(n+1);
也就是说当前元素比栈顶元素大,直接进栈,如果比其小,那么就要进行判断栈顶元素左右的个数;
class Solution {
public:
const int MOD = 1e9 + 7;
int sumSubarrayMins(vector<int>& arr) {
arr.push_back(-1);
int res = 0, len = arr.size();
stack <int> st;
for (int i = 0; i < len; i ++){
while (!st.empty() && arr[i] <= arr[st.top()]){
int index = st.top();
st.pop();
int prev = -1;
if (!st.empty())prev = st.top();
int left = index - prev;
int right = i - index;
res = (res + ((long)arr[index] * left * right) % MOD) % MOD;
}
st.push(i);
}
//3 1 2 4;
return res;
}
};
class Solution {
public:
vector<int> nextLargerNodes(ListNode* head) {
int len = 0;
stack <int> st;
vector <int> nums;
ListNode* p = head;
while (p){
nums.push_back(p->val);
p = p->next;
}
len = nums.size();
vector <int> vec(len, 0);
for (int i = 0; i < len; i ++){
while (!st.empty() && nums[i] > nums[st.top()]){
int index = st.top();
st.pop();
vec[index] = nums[i];
}
st.push(i);
}
return vec;
}
};
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。