Java数据结构与算法(盛水的容器贪心算法)

前言

. - 力扣（LeetCode）

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优或最佳的选择，以期望通过一系列的局部最优选择达到全局最优解的算法。贪心算法的核心思想是贪心选择性质和最优子结构性质。

贪心算法的基本步骤

1. 建立模型：将问题分解为一系列子问题。
2. 贪心选择：在每一步都选择在当前状态下的局部最优解。
3. 检验最优性：通过局部最优解的累积，最终得到全局最优解。

贪心算法的应用场景

贪心算法适用于那些能够证明通过局部最优选择能够达到全局最优的场景。以下是一些典型的贪心算法应用：

1. 活动选择问题：选择最多的不重叠活动。
2. 背包问题（部分背包）：选择总价值最大的物品集合。
3. 哈夫曼编码：构建最优二叉树以进行无损数据压缩。
4. 最小生成树问题：如Kruskal算法和Prim算法，用于找到图中的最小生成树。
5. 单源最短路径问题：如Dijkstra算法，用于找到图中从起点到所有其他点的最短路径。

实现原理

采用双指针移动方式，左右两边哪边低移动哪边，移动后计算容器大小。

具体代码实现

class Solution {public int maxArea(int[] height) {int left=0;int right=height.length-1;int res=0;while(left<right){int leftHigh=height[left];int rightHigh=height[right];int minHigh=Math.min(leftHigh,rightHigh);res=Math.max(res,(right-left)*minHigh);if(leftHigh<rightHigh){left++;}else{right--;}}return res;}
}

QA1: