概述
本文是(第17讲) 线性枚举(一) - 最值算法中所涉及课后习题的解答，发帖来记录自己关于这些题的理解和做题过程中思路，如果有错误，欢迎批评指正。
1.最大连续1的个数
题目：给定一个二进制数组， 计算其中最大连续 1 的个数。
主要思路：
遍历数组中的每个数，若为1则计数加一，若为0，更新最大连续的1的个数并将其存入ans中，然后将计数清空，继续遍历，由于出现0才会更新ans，若最大连续1的串出现在数组尾部，由于其后无0，不会将该部分连续1的个数更新入ans，所以最后需在循环完成后再次更新ans。
代码：
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int ans=0,temp=0;
for(auto num:nums){
if(num==1){
temp++;
}
else{
ans=max(ans,temp);
temp=0;
}
}
ans=max(ans,temp);
return ans;
}
};
2.数组中两元素的最大乘积
题目：给你一个整数数组 nums，请你选择数组的两个不同下标的数，使得对其分别减一后的两个数的乘积取得最大值。请你计算并返回该最大值。
代码：
class Solution {
public:
int maxProduct(vector<int>& nums) {
sort(nums.begin(),nums.end());
return (nums[nums.size()-1]-1)*(nums[nums.size()-2]-1);
}
};
3.寻找旋转数组中的最小值
题目：已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] ，旋转 4 次后可得到 [4,5,6,7,0,1,2]。给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素 。
主要思路：
对于这个题，完全可以使用排序加取最小值的方法，但是这样的话就没有用到旋转数组这一特性。
对于旋转数组，由于其初始状态为升序，所以它只可能有三种状态：
(1) 最小值在0位置，即升序数组；
(2) 最小值在s-1位置，即降序数组；
(3) 最小值在中间，即前降后升数组；
可以看出，它总是部分有序的，所以可以使用二分查找的方法，将下标0，s-1初始化为左右端点（s为数组长度），然后计算中点，若中点处的值大于右端点，此时说明最小值在中点和右端点之间，所以令中点加一变为了新的左端点（因为中点处的值绝对不会是最小值，起码它比右端点的值要大）；若中点处的值小于右端点，那么最小值在左端点和中点之间，此时中点变为了新的右端点（因为中点处的值可能就是最小值），不断循环遍历，直至找到最小值，最小值即为最终右端点的值。
代码：
//排序+取最小值
class Solution {
public:
int maxProduct(vector<int>& nums) {
sort(nums.begin(),nums.end());
return nums[0];
}
};
//二分查找
class Solution {
public:
int findMin(vector<int>& nums) {
int left=0,right=nums.size()-1;
while(left<right){
int mid=left+(right-left)/2;
if(nums[mid]>nums[right]){
left=mid+1;
}else if(nums[mid]<nums[right]){
right=mid;
}
}
return nums[right];
}
};
4.寻找旋转数组中的最小值II
题目：已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在旋转 4 次后可得到 [4,5,6,7,0,1,4]。给你一个可能存在重复元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
主要思路：
该题与前面一题唯一的区别就是数组中存在重复元素，这样的话在二分的时候就有额外的一种情况，即中点和右端点处的值一样，但最小值在这两点之间，例如：[3,3,3,3,3,1,1,3,3,3] 这样的数组，此时若直接忽视有部分，会导致最小值丢失，所以需要将右端点小心地回一步步回退，这样的话，它一定能退到最小值“坑”中。
代码：
class Solution {
public:
int findMin(vector<int>& nums) {
int left=0,right=nums.size()-1;
while(left<right){
int mid=left+(right-left)/2;
if(nums[mid]>nums[right]){
left=mid+1;
}else if(nums[mid]<nums[right]){
right=mid;
}
else{
right-=1;
}
}
return nums[right];
}
};
5.第三大的数
题目：给你一个非空数组，返回此数组中第三大的数 。如果不存在，则返回数组中最大的数。
主要思路：
(1) 排序+遍历，若找到第三大的数，将其返回，否则返回最大值。
(2) 使用有序集合，始终保持它的大小不超过三，此时，该集合中所存的数为数组的最大、次大、第三大值，最后若集合大小为三，就返回集合的首个元素，否则，返回集合尾部元素（集合中的元素大小顺序为升序）。
代码：
//排序+遍历
class Solution {
public:
int thirdMax(vector<int>& nums) {
sort(nums.begin(),nums.end());
int index=1;
for(int i=nums.size()-1;i>0;i--){
if(nums[i-1]!=nums[i]){
index++;
if(index==3){
return nums[i-1];
}
}
}
return nums[nums.size()-1];
}
};
//有序集合
class Solution {
public:
int thirdMax(vector<int>& nums) {
set<int> chart;
for(auto num:nums){
chart.insert(num);
if(chart.size()>3){
chart.erase(chart.begin());
}
}
return chart.size()==3? *chart.begin() : *chart.rbegin();
}
};
6.三个数的最大乘积
题目：给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
主要思路：
首先对数组排序，然后若数组全正或仅有一个负数，最大乘积值即为升序数组后三个数的乘积，若数组有两个以上负数，则最大乘积值即为升序数组前两个数和最后一个数的的乘积，综上，对于所有情况，答案为升序数组 “后三个数的乘积” 和 ”前两个数和最后一个数的的乘积“ 这两个结果中的最大值。既然如此，那么也可以不用排序，直接找出数组中最大的三个数以及最小的两个数，然后计算结果即可。
代码：
//排序
class Solution {
public:
int maximumProduct(vector<int>& nums) {
int n=nums.size();
sort(nums.begin(),nums.end());
return max(nums[0]*nums[1]*nums[n-1],nums[n-1]*nums[n-2]*nums[n-3]);
}
};
//遍历
class Solution {
public:
int maximumProduct(vector<int>& nums) {
int n=nums.size();
int max1=INT_MIN,max2=INT_MIN,max3=INT_MIN,min1=INT_MAX,min2=INT_MAX;
for(auto num:nums){
if(num<min1){
min2=min1;
min1=num;
}else if(num<min2){
min2=num;
}
}
for(auto num:nums){
if(num>max1){
max3=max2;
max2=max1;
max1=num;
}else if(num>max2){
max3=max2;
max2=num;
}else if(num>max3){
max3=num;
}
}
return max(max1*max2*max3,min1*min2*max1);
}
};
最后
以上就是直率高山为你收集整理的Leetcode刷题---线性枚举之最值算法的全部内容，希望文章能够帮你解决Leetcode刷题---线性枚举之最值算法所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复