目录
- 一、概念
- 二、模板
- 三、例题
- 题：485. 最大连续 1 的个数
- 解：
- 题：1464. 数组中两元素的最大乘积
- 解：
- 题：153. 寻找旋转排序数组中的最小值
- 解：
- 题：154. 寻找旋转排序数组中的最小值 II
- 解：
- 题：414. 第三大的数
- 解：
- 题：628. 三个数的最大乘积
- 解：
一、概念
二、模板
求n个数m个最大值（不严格）：
public int thirdMax(int[] nums) {
int a = Integer.MIN_VALUE, b = Integer.MIN_VALUE, c = Integer.MIN_VALUE; // ...
for(int num : nums) {
if(num > a) {
c = b; b = a; a = num; // 注意先后赋值顺序
}else if(num <= a && num > b) {
c = b; b = num;
}else if(num <= b && num > c) {
c = num;
}
}
return c == Integer.MIN_VALUE ? a : c;
}求n个数m个最大值（严格）：
public int thirdMax(int[] nums) {
int a = Integer.MIN_VALUE, b = Integer.MIN_VALUE, c = Integer.MIN_VALUE; // ...
for(int num : nums) {
if(num > a) {
c = b; b = a; a = num; // 注意先后赋值顺序
}else if(num < a && num > b) {
c = b; b = num;
}else if(num < b && num > c) {
c = num;
}
}
return c == Integer.MIN_VALUE ? a : c;
}三、例题
题：485. 最大连续 1 的个数
给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。
示例 1：
输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.
示例 2:
输入：nums = [1,0,1,1,0,1]
输出：2
提示：
1 <= nums.length <= 105
nums[i] 不是 0 就是 1.
解：
解题思路：枚举
AC代码：
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int maxCount = 0, count = 0;
for(int num : nums) {
if(num == 1) {
count ++;
}else {
maxCount = Math.max(maxCount, count);
count = 0;
}
}
return Math.max(maxCount, count);
}
}题：1464. 数组中两元素的最大乘积
给你一个整数数组 nums，请你选择数组的两个不同下标 i和j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。
请你计算并返回该式的最大值。
示例 1：
输入：nums = [3,4,5,2]
输出：12
解释：如果选择下标 i=1 和 j=2（下标从 0 开始），则可以获得最大值，(nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12 。
示例 2：
输入：nums = [1,5,4,5]
输出：16
解释：选择下标 i=1 和 j=3（下标从 0 开始），则可以获得最大值 (5-1)*(5-1) = 16 。
示例 3：
输入：nums = [3,7]
输出：12
提示：
2 <= nums.length <= 500
1 <= nums[i] <= 10^3
解：
解题思路：枚举
AC代码：
class Solution {
public int maxProduct(int[] nums) {
return (getMax(nums) - 1) * (getMax(nums) - 1);
}
public int getMax(int[] nums) {
int max = 0;
int p = -1;
for(int i = 0; i < nums.length; i ++) {
if(max < nums[i]){
max = nums[i];
p = i;
}
}
nums[p] = 0;
return max;
}
}题：153. 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
解：
解题思路：二分
AC代码：
class Solution {
public int findMin(int[] nums) {
int l = 0, r = nums.length - 1;
if(nums[r] > nums[l]) return nums[0];
while(l < r) {
int mid = (l + r)/ 2;
if(nums[mid] < nums[r]) r = mid;
else l = mid + 1;
}
return nums[l];
}
}题：154. 寻找旋转排序数组中的最小值 II
已知一个长度为n的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
- 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
- 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
输入：nums = [1,3,5]
输出：1
示例 2：
输入：nums = [2,2,2,0,1]
输出：0
提示：
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
进阶：
这道题是 寻找旋转排序数组中的最小值 的延伸题目。
允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
解：
解题思路：二分法
AC代码：
class Solution {
public int findMin(int[] nums) {
int l = 0, r = nums.length - 1;
while(l < r) {
int mid = (l + r) / 2;
if(nums[mid] > nums[r]) l = mid + 1; // mid不可能是答案
else if(nums[mid] < nums[r]) r = mid; // mid可能是答案
else r --;
}
return nums[l];
}
}题：414. 第三大的数
给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
示例 1：
输入：[3, 2, 1]
输出：1
解释：第三大的数是 1 。
示例 2：
输入：[1, 2]
输出：2
解释：第三大的数不存在, 所以返回最大的数 2 。
示例 3：
输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。
提示：
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
- 进阶：你能设计一个时间复杂度 O(n) 的解决方案吗？
解：
解题思路：枚举
AC代码：
class Solution {
public int thirdMax(int[] nums) {
long a = Long.MIN_VALUE, b = Long.MIN_VALUE, c = Long.MIN_VALUE; // 注意取值范围
for(long num : nums) {
if(num > a) {
c = b; b = a; a = num; // 注意先后赋值顺序
}else if(num < a && num > b) {
c = b; b = num;
}else if(num < b && num > c) {
c = num;
}
}
return c == Long.MIN_VALUE ? (int)a : (int)c;
}
}题：628. 三个数的最大乘积
给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
示例 1：
输入：nums = [1,2,3]
输出：6
示例 2：
输入：nums = [1,2,3,4]
输出：24
示例 3：
输入：nums = [-1,-2,-3]
输出：-6
提示：
3 <= nums.length <= 104
-1000 <= nums[i] <= 1000
解：
解题思路：
分三种情况：
- 全为正数：res = max1 * max2 * max3
- 全为负数：res = max1* max2* max3
- 有正有负：res = max(max1 * max2 * max3(两正一负), min1 * min2 * max1(两负一正))
值得注意的是：这里的最大最小不严格，可以相等。
AC代码：
class Solution {
public int maximumProduct(int[] nums) {
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
for(int num : nums) {
// 寻找前三个max(不严格，相等也算)
if(num > max1) {
max3 = max2; max2 = max1; max1 = num;
}else if(num <= max1 && num > max2) {
max3 = max2; max2 = num;
}else if(num <= max2 && num > max3){
max3 = num;
}
// 寻找后两个min(不严格，相等也算)
if(num < min1) {
min2 = min1; min1 = num;
}else if(num < min2 && num >= min1) {
min2 = num;
}
}
return Math.max(max1 * max2 * max3, min1 * min2 * max1);
}
}