public class MinStack
{
Stack<int> stack;
Stack<int> minStack;
public MinStack()
{
stack = new Stack<int>();
minStack = new Stack<int>();
}
public void Push(int val)
{
stack.Push(val);
if (minStack.Count == 0 || val <= minStack.Peek())
{
minStack.Push(val);
}
}
public void Pop()
{
int val = stack.Pop();
if (minStack.Peek() == val)
{
minStack.Pop();
}
}
public int Top()
{
return stack.Peek();
}
public int GetMin()
{
return minStack.Peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.Push(val);
* obj.Pop();
* int param_3 = obj.Top();
* int param_4 = obj.GetMin();
*/
逆波兰表达式求值
请你计算该表达式。返回一个表示表达式值的整数。
思路：通过栈保存原来的元素，遇到表达式弹出运算，再推入结果，重复这个过程
public int EvalRPN(string[] tokens)
{
Stack<int> stack = new Stack<int>();
int length = tokens.Length;
for (int i = 0; i < length; i++)
{
string token = tokens[i];
if (IsNumber(token))
{
stack.Push(int.Parse(token));
}
else
{
int num2 = stack.Pop();
int num1 = stack.Pop();
switch (token)
{
case "+":
stack.Push(num1 + num2);
break;
case "-":
stack.Push(num1 - num2);
break;
case "*":
stack.Push(num1 * num2);
break;
case "/":
stack.Push(num1 / num2);
break;
}
}
}
return stack.Pop();
}
public bool IsNumber(string token)
{
return char.IsDigit(token[^1]);
}
字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
思路：通过栈辅助进行操作
public string DecodeString(string s)
{
StringBuilder sb = new StringBuilder();
Stack<int> stack = new Stack<int>();
int num = 0;
int length = s.Length;
for (int i = 0; i < length; i++)
{
char c = s[i];
if (char.IsDigit(c))
{
num = num * 10 + c - '0';
}
else if (char.IsLetter(c))
{
sb.Append(c);
}
else if (c == '[')
{
stack.Push(num);
num = 0;
sb.Append(c);
}
else
{
int top = sb.Length - 1;
StringBuilder temp = new StringBuilder();
while (sb[top] != '[')
{
temp.Append(sb[top]);
sb.Length = top;
top--;
}
sb.Length = top;
StringBuilder temp2 = new StringBuilder();
for (int j = temp.Length - 1; j >= 0; j--)
{
temp2.Append(temp[j]);
}
int k = stack.Pop();
for (int j = 0; j < k; j++)
{
sb.Append(temp2);
}
}
}
return sb.ToString();
}
public int LargestRectangleArea(int[] heights)
{
int length = heights.Length;
int[] left = new int[length];
int[] right = new int[length];
Array.Fill(left, -1);
Array.Fill(right, length);
Stack<int> stack = new Stack<int>();
for (int i = 0; i < length; i++)
{
int height = heights[i];
while (stack.Count > 0 && heights[stack.Peek()] >= height)
{
right[stack.Pop()] = i;
}
if (stack.Count > 0)
{
left[i] = stack.Peek();
}
stack.Push(i);
}
int area = 0;
for (int i = 0; i < length; i++)
{
area = Math.Max(area, (right[i] - left[i] - 1) * heights[i]);
}
return area;
}
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
public int Trap(int[] height)
{
int amount = 0;
Stack<int> stack = new Stack<int>();
int n = height.Length;
for (int i = 0; i < n; i++) {
while (stack.Count > 0 && height[stack.Peek()] <= height[i]) {
int curr = stack.Pop();
if (stack.Count == 0) {
break;
}
int prev = stack.Peek();
int currWidth = i - prev - 1;
int currHeight = Math.Min(height[prev], height[i]) - height[curr];
amount += currWidth * currHeight;
}
stack.Push(i);
}
return amount;
}
