1. 问题

数组中的最大值和次大值

输入：A[1…n]=<a1, a2, …, an>
输出：max1，max2

【注：max1表示最大值，max2表示次大值】

2. 代码

// max1 和 max2首先均被初始化为int范围内最小值，
// 并且保证数组A[1..n]中的任何一个值比int范围内最小值都大。
for (int i = 1; i <= n; i++) {
	if (A[i] > max1) {
		max2 = max1;
		max1 = A[i];
	} else if (A[i] > max2) {
		max2 = A[i];
	}
}

3. 算法正确性证明

算法证明所用技术：循环不变式

证明要点：
初始化： 首先证明在第3次循环之前，循环不变式成立。即，对于数组中前2 $(3-1=2)$个数，max1中存储最大值，max2存储次大值。
保持： 证明从第3次循环往后，每次迭代保持循环不变式。即，如果第k次执行之前，循环不变式（对于数组前 $k-1$ 个数，max1中存储最大值，max2存储次大值）成立，第k+1次执行之前，循环不变式（对于数组前 $k+1-1$ 个数，max1中存储最大值，max2存储次大值，）仍然成立。
终止： 最后研究在循环终止时发生了什么。导致循环终止的条件是i <= n。我们有：对于数组中的前n个数，max1存储最大值，max2存储次大值。

我们在这里仅证明保持部分。
第k次执行循环体之前： 对于数组前k-1个数，max1存储最大值，max2存储次大值。
第k次执行循环体： 分支1，若A[k]>max1，则执行max2 = max1; max1 = A[k]。 由于max1存储的是前k-1个数的最大值，因此，前k个数的次大值就是max1，所以将max1的值转存至max2。而将A[k]存入max2，这样，max1存储的就是前k个数的最大值了。分支2，若max1>A[k]>max2，则执行max2 = A[k]。由于max1比A[k]大，所以，前k个数的最大值依然是max1，所以max1的值不变。但A[k]比max2大，并且又因为max2存储的是前k-1个数的次大值，因此比当前max2大的数只有max1和A[k]，又因为max1大于A[k]，所以，A[k]是前k个数的次大值。故需要将A[k]的值转存至max2。
第k+1次执行循环体之前： 对于数组前k个数，max1存储最大值，max2存储次大值。

解题思路：

假设数组中的第一个数和第一个下标是最大值，按照打擂主的形式进行一一比较，如果max<array[i]时，那么此时array[i]就是max，即max=array[i]。那么此时最大下标就是maxIdex=i 。这就是本题的思路。

最小值和最小值的下标同理。

例题：随机一个数组，找出数组中最大的数和最大数的位置，通过打擂台的方式

 int len = (int) (Math.random() * 10 + 1);
        int[] array = new int[len];
        for (int i = 0; i < len; i++) {
            array[i] = (int) (Math.random() * 10 + 1);
        }
        System.out.println("数组的内容是：");
        for (int i = 0; i < len; i++) {
            System.out.print(array[i]+"\t");
        }
        //找出最大值
        int maxIdex=0;//假设数组中第一个数的下标是最大数的位置
        int max = array[0];//假设数组中第一个数是最大值
        for (int i = 1; i <len ; i++) {
            if (max < array[i]) {
                max = array[i];//你赢了，你是擂主
                maxIdex=i;
            }
        }
        System.out.println("\n"+"数组中的最大值是："+max);
        System.out.println("数组中最大数的下标是："+maxIdex);

例2：随机一个数组，找出数组中最小的数和最小数的位置，通过打擂台的方式

int len=(int)(Math.random()*10+1);
        int[] array=new int[len];
        for (int i = 0; i < len; i++) {
            array[i]=(int)(Math.random()*10+1);
        }
        System.out.println("数组中最小的数是：");
        for (int i = 0; i < len; i++) {
            System.out.print(array[i]+"\t");
        }
        int min=array[0];
        int minIdex=0;
        for (int i = 1; i <len ; i++) {
            if (min>array[i]){
                min=array[i];
                minIdex=i;
            }
        }
        System.out.println("\n"+"数组中最小的数是："+min);
        System.out.println("最小下标是："+minIdex);

5940. 从数组中移除最大值和最小值

给你一个下标从 0 开始的数组 nums ，数组由若干 互不相同 的整数组成。

nums 中有一个值最小的元素和一个值最大的元素。分别称为 最小值 和 最大值 。你的目标是从数组中移除这两个元素。

一次 删除 操作定义为从数组的 前面 移除一个元素或从数组的 后面 移除一个元素。

返回将数组中最小值和最大值 都 移除需要的最小删除次数。

示例 1：

输入：nums = [2,10,7,5,4,1,8,6]
输出：5
解释：
数组中的最小元素是 nums[5] ，值为 1 。
数组中的最大元素是 nums[1] ，值为 10 。
将最大值和最小值都移除需要从数组前面移除 2 个元素，从数组后面移除 3 个元素。
结果是 2 + 3 = 5 ，这是所有可能情况中的最小删除次数。

示例 2：

输入：nums = [0,-4,19,1,8,-2,-3,5]
输出：3
解释：
数组中的最小元素是 nums[1] ，值为 -4 。
数组中的最大元素是 nums[2] ，值为 19 。
将最大值和最小值都移除需要从数组前面移除 3 个元素。
结果是 3 ，这是所有可能情况中的最小删除次数。 

示例 3：

输入：nums = [101]
输出：1
解释：
数组中只有这一个元素，那么它既是数组中的最小值又是数组中的最大值。
移除它只需要 1 次删除操作。

提示：

• 1 <= nums.length <= $10^5$
• $-10^5$ <= nums[i] <= $10^5$
• nums 中的整数 互不相同

解题思路

1. 统计最大值和最小值所在的下标，因为在这题中，哪个是最大值，哪个是最小值对题目并不影响，因此我们只需要知道左边极值的下标和右边极值的下标即可。
2. 共有三种删除方法

• 从数组的 前面 移除元素，直到把右边的极值移除
• 从数组的 后面 移除元素，直到把左边的极值移除
• 从数组的两边一齐移除元素，直到把左边和右边的极值移除

代码

class Solution {
public:
    int minimumDeletions(vector<int>& nums) {

        int max_i(0),min_i(0),n=nums.size();
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i]>nums[max_i])
                max_i=i;
            if (nums[i]<nums[min_i])
                min_i=i;
        }
        int l=min(max_i,min_i),r=max(max_i,min_i);

        return min(l+1+n-r,min(r+1,n-l));

    }
};