算法练习笔记——栈的常用方法以及算法练习

悠悠 2024-03-30 18:02 78阅读 0赞

#### 栈学习 ####

*  常用方法介绍
 *  力扣练习
 *   *  力扣 20. 有效的括号
     *  力扣 32. 最长有效括号

## 常用方法介绍 ##

Stack<Character> characters = new Stack<>();
            //判断栈是否为空
            boolean empty = characters.empty();
            //将a压入栈底，同时也返回a
            Character push = characters.push('a');
            //返回栈顶的元素但是并不会删除它
            Character peek = characters.peek();
            //返回栈顶的元素，并将它删除
            Character pop = characters.pop();
            //在堆栈中搜索a，如果发现了，则返回它相对于栈顶
            //的偏移量。否则，返回-1。
            int search = characters.search('a');
            boolean empty1 = characters.isEmpty();

## 力扣练习 ##

### 力扣 20. 有效的括号 ###

![在这里插入图片描述][d2a72980a4ae408caf8a332b00af6581.png]  
解法一

class Solution {
        
        Stack<Character> characters = new Stack<>();
        public boolean isValid(String s) {
        
           char[] chars = s.toCharArray();
           for(int i=0;i<s.length();i++)
           {
        
            if(chars[i]=='(') characters.push(')');
            else if(chars[i]=='{') characters.push('}');
            else if(chars[i]=='[') characters.push(']');
            else if(characters.isEmpty()||chars[i]!=characters.pop()) return false;
           }
           return characters.isEmpty();                                                                         
    
        }
    }

> 思路：  
> 利用到了栈的后入先出的特性  
> 利用左半边的进行判断。如果与之对应就将对应的入栈，下次如果不是左边的，就将栈里面的与之比较相同出栈。

### 力扣 32. 最长有效括号 ###

![在这里插入图片描述][ff1038da7b604059872df252b5eeb6e0.png]

class Solution {
        
        public int longestValidParentheses(String s) {
        
            int maxans=0;
            Stack<Integer> stack = new Stack<>();
            stack.push(-1);
            if(s.length()==0||s.length()==1){
        
                return 0;
            }
            char[] chars = s.toCharArray();
            for(int i=0;i<s.length();i++){
        
                if(chars[i]=='(') stack.push(i);
                else{
        
                    stack.pop();
                    if(stack.isEmpty()){
        
                         stack.push(i);
                    }
                    else{
        
                         maxans = Math.max(maxans, i-stack.peek());
                    }
                }
            }
           return maxans;
    
        }
    }

> 思路分析：  
> 首先我的第一反应是用栈，当遇到（时，将其入栈，遇到）时将栈顶元素弹出，这样可以实现（）的匹对  
> 但是需要的是找出记录出长度和找出最长字符串  
> 我们先定义一个maxans 即最长字符串  
> 接下来我们需要找出最长字符串  
> 我们可以先将字符串转为数组，利用其元素下标，求出最长字符串：  
> 思路就是我们可以将元素下标入栈，记录下最后一个不匹配的元素下标，这样两次做差就可以求出，在每一次都用数学函数找出最大的数据记录  
> 由于第一次没有元素我们可以先将-1入栈

[d2a72980a4ae408caf8a332b00af6581.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/4b7ac79058a940f792211df2b47a5ace.png
[ff1038da7b604059872df252b5eeb6e0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/cb2693e0f73442e0a81ef998bd12b825.png