Day2

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

提示：

1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1

思路：可以采用原地置换方式，目的是把数字本身放到应得的位置，比如数字序列 [4,1,2,-1,9]应该放到[1,2,-1,4,9],

其中如果遇到数字大于0且小于等于数字序列长度才会考虑置换，否则不动，最终遍历得到置换后的序列，遇到的第一个不符合位置的数字位置即为缺失的最小整数，否则如果序列上的数字都在其应有的位置，则放回长度n+1即可

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

时间复杂度：O(N)，其中 N是数组的长度。
空间复杂度：O(1)。

32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

提示：

0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'

思路：使用动态规划，我们把dp[i]定义为以s.charAt(i)结尾且包括该结尾字符的最长有效括号的长度；如果s.charAt(i)=='(',显然此时dp[i]==0,否则我们可以根据dp[i-1]计算出 pre=i-1-dp[i-1],如果s.charAt(pre)=='('，证明当前字符可以匹配pre，否则dp[i]=0;此外，如果形如()()这样的形式，我们还要再加上dp[pre-1]的长度。最后取dp最大值即可

class Solution {
    public int longestValidParentheses(String s) {
        int n =s.length();
        if(n<2)return 0;
        int[]dp=new int[n];
        int max=0;
        for(int i=1;i<n;i++){
            if(s.charAt(i)==')'){
                int pre=i-1-dp[i-1];// 保存可能是左括号的位置
                if(pre>=0&&s.charAt(pre)=='('){
                    dp[i]=dp[i-1]+2;
                    if(pre-1>=0){
                        dp[i]+=dp[pre-1];
                    }
                    max=Math.max(max,dp[i]);
                }
            }
        }
        return max;
    }
}

时间复杂度： O(n)，其中 n 为字符串的长度。我们只需遍历整个字符串一次，即可将 dp数组求出来。

空间复杂度： O(n)。我们需要一个大小为 n 的 dp 数组。

977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序

思路：使用O(n)的时间复杂度，因为该数组非递减，故在负数区域的平方是递减的，而在正数区域是递增的，可以看做两个有序数组的合并，故同一般的合并有序数组不同，我们在这题可以采用双指针，开辟一个额外数组空间，比较后逆序放入即可

class Solution {
    public int[] sortedSquares(int[] nums) {
         int n=nums.length;
         int[]ans=new int[n];
         //双指针
         for(int i=0,j=n-1,pos=n-1;i<=j;){
             if(nums[i]*nums[i]>nums[j]*nums[j]){
                 ans[pos--]=nums[i]*nums[i];
                 i++;
             }
             else{
                 ans[pos--]=nums[j]*nums[j];
                 j--;
             }
         }
         return ans;
    }
}

时间复杂度：O(n)

空间复杂度：O(n)

Day2