LeetCode学习之路:栈(1)

    科技2022-07-27  104

    奔涌的LeetCoder(三):栈(1)

    这是阿茄的LeetCode学习之路系列推文“奔涌的LeetCoder”的第三讲的第一节,将介绍数据结构中栈相关问题的解法,本讲总共整理3道题。

    20.有效的括号[简单]

    说明:

    给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足:

    左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。

    示例:

    输入: "(]" 输出: false 输入: "([)]" 输出: false

    解答:

    解法一:利用栈来完成匹配

    class Solution { public boolean isValid(String s) {         //空字符串判断为真         if(s.isEmpty())             return true;         Stack<Character> stack=new Stack<Character>();         for(char c:s.toCharArray()){             if(c=='(')                 stack.push(')');             else if(c=='{')                 stack.push('}');             else if(c=='[')                 stack.push(']');             //核心语句:当首字符为右括号直接false             //当遇到右括号时但与栈顶元素不一致时,fslae             else if(stack.empty()||c!=stack.pop())                 return false;         }         //以上操作完如果时空栈说明完全匹配,true         if(stack.empty())             return true;         return false;     } } **注:遇到这种匹配的问题也可以考虑采用HashMap来存储匹配对**

    解法二:也算蛮有意思的一种解法,匹配对替换成空字符串

    class Solution {     public boolean isValid(String s) {         while(s.contains("()")||s.contains("[]")||s.contains("{}")){             if(s.contains("()")){                 s=s.replace("()","");             }             if(s.contains("{}")){                 s=s.replace("{}","");             }             if(s.contains("[]")){                 s=s.replace("[]","");             }         }         return s.length()==0;     } }

    739.每日温度[中等]

    说明:

    请根据每日气温列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0 来代替。

    示例:

    例如,给定一个列表temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。 注:列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。

    解答:

    解法一:最直接的暴力解法,逐一遍历比较大小,时间复杂度很高

    class Solution {     public int[] dailyTemperatures(int[] T) {         int []arr = new int[T.length];         for(int i = 0; i < T.length; i ++){             int j = i;             int k = 0;             while(T[i] >= T[j]){                 k++;                 j++;                 if(j >= T.length){                     k = 0;                     break;                 }             }             arr[i] = k;         }         return arr;     } }

    解法二:第二种遍历搜索,但是经过剪枝优化,从后往前遍历,时间复杂度比第一种解法要强势很多

    class Solution {      public int[] dailyTemperatures(int[] T) {         int[] arr = new int[T.length];         //从后面开始查找         for (int i = arr.length - 1; i >= 0; i--) {             int j = i + 1;             while (j < arr.length) {                 if (T[j] > T[i]) {                     //如果找到就停止while循环                     arr[i] = j - i;                     break;                 } else if (arr[j] == 0) {                     //如果没找到,并且arr[j]==0。说明第j个元素后面没有                     //比第j个元素大的值,因为这一步是第i个元素大于第j个元素的值,                     //那么很明显这后面就更没有大于第i个元素的值。直接终止while循环。                     break;                 } else {                     //如果没找到,并且arr[j]!=0说明第j个元素后面有比第j个元素大的值,                     //然后我们让j往后挪arr[j]个单位,找到那个值,再和第i个元素比较                     j += arr[j];                 }             }         }         return arr;     } }

    解法三:单调栈

    class Solution {     public int[] dailyTemperatures(int[] T) {         //创建辅助栈,用于存储数组T下标         Stack<Integer> stack = new Stack<>();         int[] arr = new int[T.length];         for (int i = 0; i < T.length; i++) {             //代码核心:单调栈,保持栈顶到栈top到bottom元素对应的值单调(此题为单调递增)             //让小项出栈,大项入栈             while (!stack.isEmpty() && T[i] > T[stack.peek()]) {                 int idx = stack.pop();                 arr[idx] = i - idx;             }             stack.push(i);         }         return arr;     } }

    503. 下一个更大元素II[中等]

    说明:

    给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1。

    示例:

    输入: [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2; 数字 2 找不到下一个更大的数;  第二个 1 的下一个最大的数需要循环搜索,结果也是 2。

    解答:

    解法一:单调栈。

    class Solution {     public int[] nextGreaterElements(int[] nums) {         int[] res = new int[nums.length];         Arrays.fill(res, -1);         Stack<Integer> stack = new Stack<>();   // 存储的是索引index         // 由于是循环数组,对于末位元素,要往后循环考虑到其前一位数也就是倒数第二个数         for(int i = 0; i < 2 * nums.length; i++) {             // 对于当前元素,弹出栈中小于当前元素的元素,这些被弹出的元素的"下一个更大元素"就是当前元素             // 一个元素只有入栈后再被弹出,才能得到该元素的"下一个更大元素",否则无"下一个更大元素",res[i]默认为-1             // 例如,对于最大的元素,其一直留在栈中无法被弹出,因此其"下一个更大元素"默认为-1             while(!stack.empty() && nums[stack.peek()] < nums[i % nums.length])                 res[stack.pop()] = nums[i % nums.length];             stack.push(i % nums.length);         }          return res;     } }

    注:判别是否需要使用单调栈,如果需要找到左边或者右边第一个比当前位置的数大或者小,则可以考虑使用单调栈。 学习记录会在公众号同步更新,欢迎关注!

    Processed: 0.011, SQL: 8