Leetcode stack related

q20 Valid parenthesis

Valid parenthesis

Answer key

Traversal string , Use stack to save left parenthesis , When the right bracket is encountered , Compare it with the element at the top of the stack .

func isValid(s string) bool {
    
	var stack []byte
	for i := 0; i < len(s); i++ {
    
		if s[i] == '(' || s[i] == '[' || s[i] == '{' {
    
			stack = append(stack, s[i])
		}
		if len(stack) == 0 {
    
			return false
		}
		if s[i] == ')' {
    
			if stack[len(stack) - 1] == '(' {
    
				stack = stack[:len(stack) - 1]
			} else {
    
				return false
			}
		}
		if s[i] == ']' {
    
			if stack[len(stack) - 1] == '[' {
    
				stack = stack[:len(stack) - 1]
			} else {
    
				return false
			}
		}
		if s[i] == '}' {
    
			if stack[len(stack) - 1] == '{' {
    
				stack = stack[:len(stack) - 1]
			} else {
    
				return false
			}
		}
	}
    if len(stack) != 0 {
    
		return false
	}
	return true
}

q32 Longest valid bracket

Subject portal

Answer key

This problem can be solved by stack , Use the following strategies ：
1. The position of brackets in the stack
2. The stack base stores the position of the last redundant right parenthesis , Easy to count , Initially press -1
3. When encountering the closing parenthesis, a value must pop up first , And then determine ：

• If the element in the stack is empty after popping , Then update the position of the last redundant right parenthesis
• If it's not empty , Then update the length of the longest valid bracket , The method is to subtract the subscript of the element at the top of the stack from the current subscript

func longestValidParentheses(s string) int {
    
	maxLength := 0
	stack := []int{
    -1}
	for i := 0; i < len(s); i++ {
    
		//  If it's left parenthesis , Directly stack the position 
		if s[i] == '(' {
    
			stack = append(stack, i)
		} else {
    
			//  Anyway , First pop up an element 
			stack = stack[:len(stack) - 1]
			//  What pops up is the stack base element , Then update the subscript of the last redundant right parenthesis 
			if len(stack) == 0 {
    
				stack = append(stack, i)
			//  What pops up is not the stack base , Update Max 
			} else {
    
				if maxLength < i - stack[len(stack) - 1] {
    
					maxLength = i - stack[len(stack) - 1]
				}
			}
		}
	}
	return maxLength
}

q155 Smallest stack

Subject portal

Answer key

The requirement of this problem is to find the minimum value with constant time complexity , I use an auxiliary stack to solve it .
MinStack There are two stacks in the structure , A main stack , Used to store elements , An auxiliary stack , Used to store minimum value , The top of the auxiliary stack is used to store the current minimum .
Each time the auxiliary stack is pressed, the minimum value between the current main stack and the newly pressed element . So that's a guarantee , If the minimum value of the main stack is at the top of the stack , Behind the bomb stack , The auxiliary stack also pops up accordingly , At this time, the top of the auxiliary stack is still the minimum value of all current elements .

As shown in the figure ：

type MinStack struct {
    
	stack []int
	minStack []int
}


func Constructor() MinStack {
    
	return MinStack{
    
		stack: make([]int, 0),
		minStack: []int{
    math.MaxInt32},
	}
}


func (this *MinStack) Push(val int)  {
    
	this.stack = append(this.stack, val)
	if val < this.minStack[len(this.minStack) - 1] {
    
		this.minStack = append(this.minStack, val)
	} else {
    
		this.minStack = append(this.minStack, this.minStack[len(this.minStack) - 1])
	}
}


func (this *MinStack) Pop()  {
    
	this.stack = this.stack[:len(this.stack) - 1]
	this.minStack = this.minStack[:len(this.minStack) - 1]
}


func (this *MinStack) Top() int {
    
	return this.stack[len(this.stack) - 1]
}

func (this *MinStack) GetMin() int {
    
	return this.minStack[len(this.minStack) - 1]
}

q224 Basic calculator

Basic calculator

Answer key

This problem has only addition and subtraction , Just define a stack .res Used to save the final results ,sign Used to mark the last symbol ,num Used to store numbers .
Then traverse the string , If it is a number, it is stored in num in , If it is + Number or - Add up the previous numbers first ：res += num * sign, And then sign Set as 1 perhaps -1, then num Set as 0 that will do . If it's left parenthesis , Then first press the calculation result and the symbol before the bracket onto the stack , And then res Set as 0, Used to save the operation results in brackets . When the right bracket appears , Just compare the result saved in the stack with the calculation result in brackets res Integration .

func calculate(s string) int {
    
	stack, res, num, sign := []int{
    }, 0, 0, 1
	for i := 0; i < len(stack); i++ {
    
		if s[i] >= '0' && s[i] <= '9' {
    
			num = num * 10 + int(s[i] - '0')
		} else if s[i] == '+' {
    
			res += sign * num
			num = 0
			sign = 1
		} else if s[i] == '-' {
    
			res += sign * num
			num = 0
			sign = -1
		} else if s[i] == '(' {
    
			//  Push the previous result and symbol onto the stack 
			stack = append(stack, res)
			stack = append(stack, sign)
			//  Set the result to 0,  Just calculate the new result in brackets 
			res = 0
			sign = 1
		} else if s[i] == ')' {
    
			res += sign * num
			num = 0
			res *= stack[len(stack) - 1]
			res += stack[len(stack) - 2]
			stack = stack[:len(stack) - 2]
		}
	}
	//  It ends with either a right parenthesis or a number 
	if num != 0 {
    
		res += sign * num
	}
	return res
}

q232 Using stack to realize queue

Subject portal

Answer key

The title provides two stacks , One as a team stack stack1, Press in every time you join the team stack1; One as a team stack stack2, Every time I have to go out of the team , First judge stack2 Is it empty , If it is empty , will stack1 All elements in are pressed stack2 in , Then pop up the top element ; If it's not empty , Just pop up the top element of the stack . Just right, you can implement the queue first in first out feature .
The same is true of the return queue header element .
If two stacks are empty at the same time , Then the queue is empty .

type MyQueue struct {
    
	stack1, stack2 []int
}

func Constructor() MyQueue {
    
	return MyQueue{
    }
}

func (this *MyQueue) Push(x int)  {
    
	this.stack1 = append(this.stack1, x)
}

func (this *MyQueue) Pop() int {
    
	if len(this.stack2) == 0 {
    
		for len(this.stack1) != 0 {
    
			this.stack2 = append(this.stack2, this.stack1[len(this.stack1) - 1])
			this.stack1 = this.stack1[:len(this.stack1) - 1]
		}
	}
	front := this.stack2[len(this.stack2) - 1]
	this.stack2 = this.stack2[:len(this.stack2) - 1]
	return front
}


func (this *MyQueue) Peek() int {
    
	if len(this.stack2) == 0 {
    
		for len(this.stack1) != 0 {
    
			this.stack2 = append(this.stack2, this.stack1[len(this.stack1) - 1])
			this.stack1 = this.stack1[:len(this.stack1) - 1]
		}
	}
	front := this.stack2[len(this.stack2) - 1]
	return front
}


func (this *MyQueue) Empty() bool {
    
	if len(this.stack1) == 0 && len(this.stack2) == 0 {
    
		return true
	} else {
    
		return false
	}
}

q316 Remove duplicate letters

Subject portal

Answer key

First, traverse the string , Record the number of times each letter appears . Then traverse the string again ,exist Array is used to mark whether the current letter already exists in the stack , If there is , Just skip. . If it does not exist, the loop is compared with the letter at the top of the stack , If the letter at the top of the stack is larger than the current letter, and there is also a top of the stack element after it , Pop up the top element of the stack . Finally, put the letters on the stack .

func removeDuplicateLetters(s string) string {
    
	var count [26]int
	var exist [26]bool
	var stack []rune
	for _, v := range s {
    
		count[v - 'a']++
	}
	for _, v := range s {
    
		if exist[v - 'a'] {
    
			count[v - 'a']--
			continue
		}
		//  If the conditions are met, it should be out of the stack 
		// 1. There are elements in the stack 
		// 2. The stack top element is larger than the current element 
		// 3. The stack top element appears later 
		for len(stack) > 0 && stack[len(stack) - 1] > v && count[stack[len(stack) - 1] - 'a'] > 0 {
    
			exist[stack[len(stack) - 1] - 'a'] = false
			stack = stack[:len(stack) - 1]
		}
		stack = append(stack, v)
		count[v - 'a']--
		exist[v - 'a'] = true
	}
	return string(stack)
}