LeetCode16 最接近的三数之和
相似题目：LeetCode15 三数之和
题目详情
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：
输入：nums = [0,0,0], target = 1
输出：0
提示：
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
代码
class LeetCode16 {
public static void main(String[] args) {
System.out.println(new Solution().threeSumClosest(new int[]{-1, 2, 1, -4}, 1));
}
/*
排序+双指针
*/
static class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int best = 10000000;
// 枚举 a
for (int i = 0; i < n; ++i) {
// 保证和上一次枚举的元素不相等
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 使用双指针枚举 b 和 c
int j = i + 1, k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
// 如果和为 target 直接返回答案
if (sum == target) {
return target;
}
// 根据差值的绝对值来更新答案
if (Math.abs(sum - target) < Math.abs(best - target)) {
best = sum;
}
if (sum > target) {
// 如果和大于 target，移动 c 对应的指针
int k0 = k - 1;
// 移动到下一个不相等的元素
while (j < k0 && nums[k0] == nums[k]) {
--k0;
}
k = k0;
} else {
// 如果和小于 target，移动 b 对应的指针
int j0 = j + 1;
// 移动到下一个不相等的元素
while (j0 < k && nums[j0] == nums[j]) {
++j0;
}
j = j0;
}
}
}
return best;
}
}
}
LeetCode26 删除有序数组中的重复项
题目详情
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被 通过。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示：
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 升序 排列
代码
public class LeetCode26 {
public static void main(String[] args) {
int[] nums1 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
System.out.println("长度：" + new Solution().removeDuplicates(nums1));
System.out.println(Arrays.toString(nums1));
int[] nums2 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
System.out.println("长度：" + new Solution2().removeDuplicates(nums2));
System.out.println(Arrays.toString(nums2));
int[] nums3 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
System.out.println("长度：" + new Solution3().removeDuplicates(nums3));
System.out.println(Arrays.toString(nums3));
}
static class Solution {
//while 循环 同向双指针
public int removeDuplicates(int[] nums) {
//异常处理
if (nums == null || nums.length == 0) return 0;
//初始化i 和j
int i = 0, j = 1;
while (j < nums.length) {
//如果没有重复，保留，否则忽略
if (nums[i] != nums[j]) {
nums[i + 1] = nums[j];
i++;
}
j++;
}
return i + 1;
}
}
static class Solution2 {
// for 循环 同向双指针
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
}
static class Solution3 {
public int removeDuplicates(int[] nums) {
//标记重复元素
Set<Integer> set = new HashSet<>();
int j = 0;
for (int i = 0; i < nums.length; i++) {
if (!set.contains(nums[i])) {
nums[j++] = nums[i];
set.add(nums[i]);
}
}
return set.size();
}
}
}
LeetCode54 螺旋矩阵
题目详情
给定一个包含m x n个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例2:
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]
代码
class LeetCode54 {
public static void main(String[] args) {
System.out.println(new Solution().spiralOrder(new int[][]{
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}}));
System.out.println(new Solution2().spiralOrder(new int[][]{
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}}));
System.out.println(new Solution3().spiralOrder(new int[][]{
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}}));
}
/*
模拟
*/
static class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> order = new ArrayList<>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return order;
}
int rows = matrix.length, columns = matrix[0].length;
boolean[][] visited = new boolean[rows][columns];
int total = rows * columns;
int row = 0, column = 0;
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int directionIndex = 0;
for (int i = 0; i < total; i++) {
order.add(matrix[row][column]);
visited[row][column] = true;
int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
directionIndex = (directionIndex + 1) % 4;
}
row += directions[directionIndex][0];
column += directions[directionIndex][1];
}
return order;
}
}
/*
按层遍历
*/
static class Solution2 {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> order = new ArrayList<Integer>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return order;
}
int rows = matrix.length, columns = matrix[0].length;
int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
while (left <= right && top <= bottom) {
for (int column = left; column <= right; column++) {
order.add(matrix[top][column]);
}
for (int row = top + 1; row <= bottom; row++) {
order.add(matrix[row][right]);
}
if (left < right && top < bottom) {
for (int column = right - 1; column > left; column--) {
order.add(matrix[bottom][column]);
}
for (int row = bottom; row > top; row--) {
order.add(matrix[row][left]);
}
}
left++;
right--;
top++;
bottom--;
}
return order;
}
}
/*
顺时针顺序
n++,m++,n--,m-- 这样循环的来
*/
static class Solution3 {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList<>();
//总元素
int num = matrix.length * matrix[0].length;
int i = 0, j = 0;
int count = 0;
//0,1,2,4 右，下，左，上
int arrow = 0;
int mBottom = matrix.length;
int mTop = -1;
int nRight = matrix[0].length;
int nLeft = -1;
while (count < num) {
if (i < matrix.length && j < matrix[0].length) {
ans.add(matrix[i][j]);
count++;
}
if (arrow == 0) {//右
j++;
} else if (arrow == 1) {//下
i++;
} else if (arrow == 2) {//左
j--;
} else if (arrow == 3) {//上
i--;
}
if (j == nRight) {//撞到右墙
arrow = 1;
nRight--;
j--;
}
if (i == mBottom) {//撞到下墙
arrow = 2;
mBottom--;
i--;
}
if (i == nLeft) {//撞到左墙
arrow = 3;
mBottom++;
i++;
}
if (j == mTop) {//撞到上墙
arrow = 0;
nLeft++;
j++;
}
}
return ans;
}
}
}
LeetCode57 插入区间
LeetCode56 合并区间
题目详情
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
代码
class LeetCode57 {
public static void main(String[] args) {
System.out.println(Arrays.deepToString(new Solution().insert(new int[][]{{1, 3}, {6, 9}}, new int[]{2, 5})));
}
static class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
int left = newInterval[0];
int right = newInterval[1];
boolean placed = false;
List<int[]> ansList = new ArrayList<int[]>();
for (int[] interval : intervals) {
if (interval[0] > right) {
// 在插入区间的右侧且无交集
if (!placed) {
ansList.add(new int[]{left, right});
placed = true;
}
ansList.add(interval);
} else if (interval[1] < left) {
// 在插入区间的左侧且无交集
ansList.add(interval);
} else {
// 与插入区间有交集，计算它们的并集
left = Math.min(left, interval[0]);
right = Math.max(right, interval[1]);
}
}
if (!placed) {
ansList.add(new int[]{left, right});
}
int[][] ans = new int[ansList.size()][2];
for (int i = 0; i < ansList.size(); ++i) {
ans[i] = ansList.get(i);
}
return ans;
}
}
}
LeetCode66 加一
题目详情
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
示例 2：
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
示例 3：
输入：digits = [0]
输出：[1]
提示：
1 <= digits.length <= 100
0 <= digits[i] <= 9
代码
public class LeetCode66 {
public static void main(String[] args) {
System.out.println(Arrays.toString(new Solution().plusOne(new int[]{9, 9, 9})));
System.out.println(Arrays.toString(new Solution2().plusOne(new int[]{9, 9, 9})));
System.out.println(Arrays.toString(new Solution3().plusOne(new int[]{9, 9, 9})));
}
static class Solution {
public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
digits[i]++;
digits[i] = digits[i] % 10;
if (digits[i] != 0) return digits;
}
digits = new int[digits.length + 1];
digits[0] = 1;
return digits;
}
}
/*
官网答案
*/
static class Solution2 {
public int[] plusOne(int[] digits) {
int n = digits.length;
for (int i = n - 1; i >= 0; --i) {
if (digits[i] != 9) {
++digits[i];
for (int j = i + 1; j < n; ++j) {
digits[j] = 0;
}
return digits;
}
}
// digits 中所有的元素均为 9
int[] ans = new int[n + 1];
ans[0] = 1;
return ans;
}
}
/*
不用纠结某一位是不是9，而应该去判断加1之后是不是0：
*/
static class Solution3 {
public int[] plusOne(int[] digits) {
int len = digits.length;
for (int i = len - 1; i >= 0; i--) {
digits[i] = (digits[i] + 1) % 10;
if (digits[i] != 0) {
return digits;
}
}
digits = new int[len + 1];
digits[0] = 1;
return digits;
}
}
}
LeetCode81 搜索旋转排序数组-二
题目详情
已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
你必须尽可能减少整个操作步骤。
示例 1：
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
示例 2：
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false
提示：
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104
进阶：
这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
代码
class LeetCode81 {
public static void main(String[] args) {
System.out.println(new Solution().search(new int[]{2, 5, 6, 0, 0, 1, 2}, 0));
}
static class Solution {
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return false;
}
int start = 0;
int end = nums.length - 1;
int mid;
while (start <= end) {
mid = start + (end - start) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[start] == nums[mid]) {
start++;
continue;
}
//前半部分有序
if (nums[start] < nums[mid]) {
//target在前半部分
if (nums[mid] > target && nums[start] <= target) {
end = mid - 1;
} else { //否则，去后半部分找
start = mid + 1;
}
} else {
//后半部分有序
//target在后半部分
if (nums[mid] < target && nums[end] >= target) {
start = mid + 1;
} else { //否则，去后半部分找
end = mid - 1;
}
}
}
//一直没找到，返回false
return false;
}
}
}
LeetCode121 买卖股票的最佳时机
题目详情
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 105
0 <= prices[i] <= 104
代码
public class LeetCode121 {
public static void main(String[] args) {
System.out.println(new Solution1().maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
System.out.println(new Solution2().maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
}
/*
我们来假设自己来购买股票。随着时间的推移，每天我们都可以选择出售股票与否。那么，假设在第 i 天，如果我们要在今天卖股票，那么我们能赚多少钱呢？
显然，如果我们真的在买卖股票，我们肯定会想：如果我是在历史最低点买的股票就好了！太好了，在题目中，我们只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。
因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。
*/
static class Solution1 {
public int maxProfit(int[] prices) {
int maxprofit = 0;
for (int i = 0; i < prices.length - 1; i++) {
for (int j = i + 1; j < prices.length; j++) {
int profit = prices[j] - prices[i];
if (profit > maxprofit)
maxprofit = profit;
}
}
return maxprofit;
}
}
static class Solution2 {
public int maxProfit(int[] prices) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minprice)
minprice = prices[i];
else if (prices[i] - minprice > maxprofit)
maxprofit = prices[i] - minprice;
}
return maxprofit;
}
}
}
LeetCode162 寻找峰值
题目详情
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
提示：
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]
代码
class LeetCode162 {
public static void main(String[] args) {
System.out.println(new Solution().findPeakElement(new int[]{1, 2, 1, 3, 5, 6, 4}));
System.out.println(new Solution2().findPeakElement(new int[]{1, 2, 1, 3, 5, 6, 4}));
System.out.println(new Solution3().findPeakElement(new int[]{1, 2, 1, 3, 5, 6, 4}));
}
//方法一: 线性扫描
static class Solution {
public int findPeakElement(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1])
return i;
}
return nums.length - 1;
}
}
//方法二：递归二分查找
static class Solution2 {
public int findPeakElement(int[] nums) {
return search(nums, 0, nums.length - 1);
}
public int search(int[] nums, int l, int r) {
if (l == r)
return l;
int mid = (l + r) / 2;
if (nums[mid] > nums[mid + 1])
return search(nums, l, mid);
return search(nums, mid + 1, r);
}
}
//方法三：迭代二分查找
static class Solution3 {
public int findPeakElement(int[] nums) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r) / 2;
if (nums[mid] > nums[mid + 1])
r = mid;
else
l = mid + 1;
}
return l;
}
}
}
LeetCode164 最大间距
题目详情
给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。
您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。
示例 1:
输入: nums = [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:
输入: nums = [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。
提示:
1 <= nums.length <= 105
0 <= nums[i] <= 109
代码
class LeetCode164 {
public static void main(String[] args) {
System.out.println(new Solution().maximumGap(new int[]{3, 6, 9, 1}));
System.out.println(new Solution2().maximumGap(new int[]{3, 6, 9, 1}));
System.out.println(new Solution3().maximumGap(new int[]{3, 6, 9, 1}));
}
static class Solution {
public int maximumGap(int[] nums) {
if (nums.length < 2) return 0;
Arrays.sort(nums);
int ans = 0;
for (int i = 0; i < nums.length - 1; i++) {
ans = Math.max(ans, nums[i + 1] - nums[i]);
}
return ans;
}
}
static class Solution2 {
/*
思路二：非比较排序
想要时间复杂度稳定在线性，比较排序暂时是无能为力，所以就想到非比较排序的方法，例如 计数排序？先将所有元素统计，
不需要完成排序，直接在计数器计算相邻元素之间的差值。
*/
public int maximumGap(int[] nums) {
//计数
if (nums.length < 2) return 0;
int max = nums[0], min = nums[0], bias = 0;
for (int num : nums) {
max = Math.max(max, num);
min = Math.min(min, num);
}
bias = 0 - min;
int[] counter = new int[max - min + 1];
for (int num : nums) {
counter[num + bias]++;
}
//求最大差值，pre记录前一个元素
int ans = 0;
int pre = -1;
for (int i = 0; i < counter.length; i++) {
if (counter[i] != 0) {
if (pre != -1) {
ans = Math.max(ans, i - pre);
pre = i;
} else {
pre = i;
}
}
}
return ans;
}
}
static class Solution3 {
//思路三：桶排序
public int maximumGap(int[] nums) {
if (nums.length < 2) return 0;
//找到最小值、最大值
int max = 0, min = 0;
for (int num : nums) {
max = Math.max(max, num);
min = Math.min(min, num);
}
//计算桶大小,桶数量至少一个
int bucketSize = Math.max((max - min) / (nums.length - 1), 1);
Bucket[] buckets = new Bucket[(max - min) / bucketSize + 1];
//入桶,每个桶只关心桶内的最大值和最小值
for (int i = 0; i < nums.length; i++) {
int idx = (nums[i] - min) / bucketSize;
if (buckets[idx] == null) buckets[idx] = new Bucket();
buckets[idx].max = Math.max(nums[i], buckets[idx].max);
buckets[idx].min = Math.min(nums[i], buckets[idx].min);
}
//前一个桶的 max
int preMax = -1;
//最大间隔
int maxGap = 0;
for (int i = 0; i < buckets.length; i++) {
//桶不为空,并且不是第一个桶
if (buckets[i] != null && preMax != -1) {
//桶之间的间隔
maxGap = Math.max(maxGap, buckets[i].min - preMax);
}
//记录前一个桶的 max
if (buckets[i] != null) {
preMax = buckets[i].max;
}
}
return maxGap;
}
}
static class Bucket {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
}
}
LeetCode674 最长连续递增序列
题目详情
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
示例 2：
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。
提示：
1 <= nums.length <= 104
-109 <= nums[i] <= 109
代码
class LeetCode674 {
public static void main(String[] args) {
System.out.println(new Solution().findLengthOfLCIS(new int[]{1, 3, 5, 4, 7, 3, 4, 5, 6, 7, 8, 8, 2}));
}
static class Solution {
public int findLengthOfLCIS(int[] nums) {
if (nums == null) {
return 0;
}
if (nums.length == 1) {
return 1;
}
int res = 1, start = 0;
for (int i = 1; i < nums.length; i++) {
if (i > 0 && nums[i - 1] >= nums[i])
start = i;
res = Math.max(res, i - start + 1);
}
return res;
}
}
}
网友评论