leetcode数组（简单03）

11/16 LeetCode三道不再简单的简单数组题

485 最大连续1的个数

495 提莫攻击

414 找第三大的数

#485 最大连续1的个数

一次遍历数组，记录出现1的连续最大次数max，出现0就重新记录，如果max变大则更新max。

思路和官方解答一致。

评论区有更强的，用滑动窗口的方法，即定义左右两个指针，将两个指针中间区域比作一个窗口，通过移动指针改变窗口的大小，窗口的大小就是连续排列的个数。

当窗口中所有元素为1时，右指针右移扩大窗口；

当窗口中存在零时，计算连续序列的长度，左指针指向右指针。一定要跟着移动一格！！！

# 495 提莫攻击

一道简单的中等难度题，思路也清晰，遍历一遍数组，在每个时间节点判断中毒状态的时间如何增加：如果中毒时间已过就再加上一个持续时间；如果持续时间没过就加上距离上一次中毒到这一次中毒的时间间隔。

思路和官方一致，题解区好像也没有更好的解答。

#414 找第三大的数

这题我花了快一个小时，时间复杂度最大是O(4n)，我的思路是借鉴485题那个滑动窗口的方法，4个窗口向后滑动，先剔除重复的数、再剔除最小的数。

代码很长，我很辣鸡，这我知道。时间复杂度打败40%，空间复杂度打败75%。

现在网也不行了，看不了题解，卒。B站、微博都能进，力扣网炸了，难道菜鸡们都在晚上刷题？

我的解答

神乎其技，虽然菜、也算是举一反三吧

public static int thirdMax(int[] nums) {
    int length = nums.length;
    if (length==1){
        return nums[0];
    }
    if (length==2){
        return Math.max(nums[0],nums[1]);
    }
    if(length>3) {
        for (int r = 2; r <= length - 2; r++) {
            //先看4格窗口中是否有重复的数出现 有就前置交换
            if (nums[r - 2] == nums[r - 1] || nums[r - 2] == nums[r] || nums[r - 2] == nums[r + 1]) {
                continue;
            }
            if (nums[r - 1] == nums[r] || nums[r - 1] == nums[r + 1]) {
                nums[r - 1] = nums[r - 2];
                continue;
            }
            if (nums[r] == nums[r + 1]) {
                nums[r] = nums[r - 2];
                continue;
            }
            //没有重复的 就把最小的前置交换
            int min = nums[r - 2];
            int indmin = r - 2;
            for (int i = -2; i <= 1; i++) {
                if (nums[r + i] < min) {
                    min = nums[r + i];
                    indmin = r + i;
                }
            }
            nums[indmin] = nums[r - 2];
        }
        nums[0]=nums[length-3];
        nums[1]=nums[length-2];
        nums[2]=nums[length-1];
    }
    //相当于数组只剩下3个数
    if (nums[0]==nums[1]||nums[0]==nums[2]||nums[1]==nums[2]){
        return Math.max(Math.max(nums[0],nums[1]),Math.max(nums[0],nums[2]));
    }else{
        return Math.min(Math.min(nums[0],nums[1]),Math.min(nums[0],nums[2]));
    }
}

扣友题解

• 思路一： 借用TreeSet（红黑树）；时间复杂度：O(n * log3) == O(n) 比较好想的思路

  1、维护一个只有3个元素的TreeSet，如果大于三个元素就就把Set中的最小最小值remove掉。
  2、最后如果Set中元素小于3就返回Set最大值，否则返回最小值。

class Solution {
    public int thirdMax(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for (Integer elem : nums) {
            set.add(elem);
            if (set.size() > 3) set.remove(set.first());
        }
        return set.size() < 3 ? set.last() : set.first();   // set.last() 里面最大的元素
    }
}
作者：happy_yuxuan

点评：这个思路其实和我的出奇一致，扣友用TreeSet来去重，遍历数组将最小的元素remove掉。但是大佬用了不到10行，我用超过40行，这就是技术的区别啊。不过现阶段思路更重要、技术多练就好。

• 思路二：

1、用三个变量来存放第一大，第二大，第三大的元素的变量，分别为one, two, three；
2、遍历数组，若该元素比one大则往后顺移一个元素，比two大则往往后顺移一个元素，比three大则赋值个three；
3、最后得到第三大的元素，若没有则返回第一大的元素。

class Solution {
    public int thirdMax(int[] nums) {
        long first = Long.MIN_VALUE;
        long second = Long.MIN_VALUE;
        long third = Long.MIN_VALUE;
        for (int num : nums) {
            if(num>first){
                third = second;
                second = first;
                first = num;
            }else if(num>second&&num<first){
                third = second;
                second = num;
            }else if(num<second&&num>third){
                third = num;
            }
        }
        return third!=Long.MIN_VALUE ? new Long(third).intValue() : new Long(first).intValue();
    }
}

作者：liccil76