一、盛最多水的容器

题目：https://leetcode.cn/problems/container-with-most-water/

题目分析

不能倾倒容器就是不能将容器这样放置着去计算容量：

这道题目里容量的计算公式是：长*宽 

长度遵循“短板原则“，即两个垂直线中较短的那根的长度为长，宽为两根垂直线的横坐标之差（垂直线的条数从0开始数）

思路讲解

1.暴力枚举

首先想到的是暴力解法

这个方法替大家试过了，超时

知识补充

java中求两个数中较小值：

1.使用 Math.min() 方法（推荐）

Java 的 Math 类提供了 min() 静态方法，可以直接返回两个数中的较小值，支持int, long, float, double 等基本数值类型

public class MinExample {
    public static void main(String[] args) {
        int a = 10;
        int b = 20;
        
        // 使用 Math.min() 求较小值
        int min = Math.min(a, b);
        System.out.println("较小的数是: " + min); // 输出: 10
    }
}

2.使用三元运算符（条件运算符）

通过 条件 ? 值1 : 值2 的形式，可以简洁地比较两个数

public class TernaryExample {
    public static void main(String[] args) {
        int a = 15;
        int b = 8;
        
        // 使用三元运算符求较小值
        int min = (a < b) ? a : b;
        System.out.println("较小的数是: " + min); // 输出: 8
    }
}

2.利用单调性，使用双指针

这个方法是两个指针合伙遍历了一遍数组，所以时间复杂度为o(n)

代码

class Solution {
    public int maxArea(int[] height) {
      int right=height.length-1;
      int left=0;
      int max=0;//最大值
      while(left<right){//当它俩相遇或者交换左右位置了，说明整个数组都遍历完了，搭配也搭完了，故循环结束
        int tmp=Math.min(height[left],height[right])*(right-left);
        if(height[left]<height[right]){
            left++;
        }else{
            right--;
        }
        if(tmp>max){
            max=tmp;
        }
      }
      return max;
    }
}

二、有效三角形的个数

题目：https://leetcode.cn/problems/valid-triangle-number/description/

题目分析

组成三角形：任意两边之和大于第三边，但其实只要保证较小的两边之和大于最大的那一边就行了

思路讲解

1.暴力枚举

首先想到的是暴力解法

//伪代码
for(int i=0;i<n;i++)
 for(int j=i+1;j<n;j++)
  for(int k=j+1;k<n;k++)
    check(nums[i],nums[j],nums[k])

首先要有三层循环来搭配，则时间复杂度为o(N^3)

然后用check函数来判断能不能构成三角形

时间复杂度太大可能会超时，故不用这个解法

2.利用单调性，使用双指针

因为判断三角形可以只用保证较小的两边之和大于最大的那一边，所以先对数组进行排序（在暴力解法中，先对数组进行排序在暴力枚举，也有一定的优化效果）

思路总结：1、先固定最大的数

                  2、在最大数的左区间里，使用双指针算法，统计出符合要求的三元组的个数

                  3、将所有的数都作为最大数固定过了，统计就结束了(其实不需要把所有数都固定一遍，因为三元组需要三个数据，所以固定到第三个数时就可以结束了）

时间复杂度：o(n^2)    因为只需要两层循环

代码

class Solution {
    public int triangleNumber(int[] nums) {
        //先进行优化--排序
        Arrays.sort(nums);
        int num=0;//定义三元组个数
        int n=nums.length;
        for(int i=n-1;i>=2;i--){//nums[i]就是固定的最大数
        int left=0;
        int right=i-1;//在这里面定义双指针，两个指针才能在第二层循环结束之后重置正确
        while(right>left){
            if(nums[left]+nums[right]>nums[i]){
                num+=right-left;
                right--;
            }else{
                left++;
            }
        }
     }
     return num;
}



/*
    因为双指针的指向在每次第二层循环结束之后要重置，所以双指针最好不要定义在循环外部
        //先进行优化--排序
        Arrays.sort(nums);
        int max=nums.length-1;//刚开始时最大数的下标
        int right=nums.length-2;//刚开始时最大数左区间里的最右边的下标
        int left=0;//刚开始时最大数左区间里的最左边的下标
        int num=0;//能组成三角形的组数
        for(int i=max;i>=2;i--){
            int c=nums[i];
            int a=nums[left];
            int b=nums[right];
            while(right>left){
                if(a+b>c){
                    num+=right-left;
                    right--;
                }else{
                    left++;
                }
            }
        }
        return num;
    }
*/
}