Day1 ：最小栈 https://leetcode-cn.com/problems/min-stack/
线性栈只能从栈顶插入、删除、取值，可以使用两个栈，一个正常插入删除数据，一个存放最小值，但是这样比较浪费空间，看到评论区有两栈共享空间，即双向栈的方式，但是这种方式必须固定数组长度，还有更为巧妙地方式，采用链表，每次插入都操作两个节点，一个存放最小值一个存放插入值。
Day2 ：有效的括号 https://leetcode-cn.com/problems/valid-parentheses/
思路：利用线性栈只能从一头插入和删除，如果按顺序入栈，规则是如果入栈元素和前一个元素配对成功则出栈，不配对入栈，操作完所有元素变成空栈则返回true.
public class Solution {
public bool IsValid(string s) {
var stack = new Stack<char>();
foreach(char c in s){
switch (c)
{
case '(':
case '{':
case '[':
stack.Push(c);
break;
case ')':
if (stack.Count == 0 || stack.Pop() != '(')
{ return false; }
break;
case '}':
if (stack.Count == 0 || stack.Pop() != '{')
{ return false; }
break;
case ']':
if (stack.Count == 0 || stack.Pop() != '[')
{ return false; }
break;
}
}
return stack.Count>0?false:true;
}
}
Day3 ： 用栈实现队列 https://leetcode-cn.com/problems/implement-queue-using-stacks/
栈：后进先出（LIFO）；队列：先进先出（FIFO）
用数组List实现队列比较简单，用栈实现，则需要两个相反序列的栈，一个进站，一个用于出栈
public class MyQueue {
/** Initialize your data structure here. */
private List<int> list;
public MyQueue() {
list = new List<int>();
}
/** Push element x to the back of queue. */
public void Push(int x) {
list.Add(x);
}
/** Removes the element from in front of queue and returns that element. */
public int Pop() {
var result = list[0];
list.RemoveAt(0);
return result;
}
/** Get the front element. */
public int Peek() {
return list[0];
}
/** Returns whether the queue is empty. */
public bool Empty() {
return list.Count()==0;
}
}
栈的方法
public class MyQueue {
/** Initialize your data structure here. */
private Stack<int> queue = new Stack<int>();
public MyQueue() {
}
/** Push element x to the back of queue. */
public void Push(int x) {
Stack<int> tmp = new Stack<int>(); //借助tmp完成入栈
int count = queue.Count;
for(int i=0; i<count; i++){
tmp.Push(queue.Pop());
}
tmp.Push(x);
++count;
for(int i=0; i<count; i++){
queue.Push(tmp.Pop());
}
tmp = null;
}
/** Removes the element from in front of queue and returns that element. */
public int Pop() {
return queue.Pop();
}
/** Get the front element. */
public int Peek() {
return queue.Peek();
}
/** Returns whether the queue is empty. */
public bool Empty() {
return queue.Count == 0;
}
}
Day 4： 下一个更大元素 https://leetcode-cn.com/problems/next-greater-element-i/
总是按顺序比较，两个数组需要两个栈，一个从头依次取nums1，一个从头依次取nums2，使用了一个filled标志位，用来判断循环完成是否赋值，如果没有则赋值-1
public class Solution {
public int[] NextGreaterElement(int[] nums1, int[] nums2) {
int[] result=new int[nums1.Length];
Console.WriteLine(result);
for(var r=0;r<nums1.Length; r++){
var filled = false;
for(int i=0;i<nums2.Length-1;i++){
if(nums1[r]==nums2[i]){
for(int j=i+1;j<nums2.Length;j++){
if(nums1[r]<nums2[j]){
result[r]=nums2[j];
filled=true;
break;
}
}
}
}
if(!filled){
result[r]=-1;
}
}
return result;
}
}
Day 5：比较含退格的字符串 https://leetcode-cn.com/problems/backspace-stringcompare/
Day 6：逆波兰表达式求值 https://leetcode-cn.com/problems/evaluate-reverse-polishnotation/
网友评论