力扣爆刷第85天之hot100五连刷11-15

力扣爆刷第85天之hot100五连刷11-15

文章目录

• • • 力扣爆刷第85天之hot100五连刷11-15
    • 一、239. 滑动窗口最大值
    • 二、76. 最小覆盖子串
    • 三、53. 最大子数组和
    • 四、56. 合并区间
    • 五、189. 轮转���组

      一、239. 滑动窗口最大值

      题目链接：https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked

      （）

      思路：求滑动窗口内的最大值，自然要维护一个滑动窗口，这里我们使用一个队列来表示滑动窗口，既然要记录最大值，那么我们在添加元素时，自然要如果队尾元素小于当前元素，队尾元素就应该出队，直到没有小于当前元素的存在，然后把当前元素入队，这样队头位置就是滑动窗口内的最大值。

      class Solution {   public int[] maxSlidingWindow(int[] nums, int k) {        int[] res = new int[nums.length - k + 1];        Queue queue = new Queue();        for (int i = 0; i  stack.getLast()) {                stack.pollLast();            }            stack.addLast(n);        }        void pop(int n) {            if (n == stack.getFirst()) {                stack.pollFirst();            }        }        int getMax() {            return stack.getFirst();        }    }}

      二、76. 最小覆盖子串

      题目链接：https://leetcode.cn/problems/minimum-window-substring/?envType=study-plan-v2&envId=top-100-liked

      （）

      思路：最小覆盖子串问题，很显然是滑动窗口，如下代码就是滑动窗口的模板。首先是一直扩大窗口，当窗口满足条件后，就开始缩小窗口，直到窗口不再满足条件，即又开始扩大窗口。

      class Solution {     public String minWindow(String s, String t) {        Map need = new HashMap();        Map window = new HashMap();        for(char c : t.toCharArray()) {            need.put(c, need.getOrDefault(c, 0) + 1);        }        int left = 0, right = 0, min = Integer.MAX_VALUE, vaild = 0;        int[] xy = new int[2];        while(right  
      三、53. 最大子数组和
       
      题目链接：https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-100-liked
      思路：本题可以使用贪心算法和动态规划，贪心如下，如果子数组和大于零，就一直加并记录最大值，这个过程中是肯能达到最大值的，只要子数组和小于零，就可以另起一个新子数组了。
       
      贪心算法：
       
      class Solution {     public int maxSubArray(int[] nums) {        int max = Integer.MIN_VALUE, sum = 0;        for(int i = 0; i  
      动态规划：定义dp[i]表示区间[0, i]中以nums[i]为结尾的最大子数组和，动态规划就是选择，可以选择是否以讲当前元素加入左边的子数组，不加入就单开一个子数组。dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
       
      class Solution {     public int maxSubArray(int[] nums) {        int[] dp = new int[nums.length];        dp[0] = nums[0];        int max = nums[0];        for(int i = 1; i  
      四、56. 合并区间
       
      题目链接：https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked
      思路：合并区间也是一个经典题目，只需要把左边界排序，只要有重叠的，就合并，无重叠就保存之前的区间，然后新开一个区间。
       
      class Solution {    public int[][] merge(int[][] intervals) {        Arrays.sort(intervals, (a, b) -> a[0]-b[0]);        List list = new ArrayList();        int left = intervals[0][0], right = intervals[0][1];        for(int i = 1; i