canvas网站源码,深圳网页制作服务,网站关键词如何收录,网络传媒有限公司盛最多水的容器
原题目链接:点击跳转
给定一个长度为 n 的整数数组 height 。有 n 条垂线#xff0c;第 i 条线的两个端点是 (i, 0) 和(i, height[i]) 。
找出其中的两条线#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说…盛最多水的容器
原题目链接:点击跳转
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和(i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明你不能倾斜容器。 提示
n height.length2 n 1050 height[i] 104
题解
设两指针 i , j 指向的水槽板高度分别为 h[i] , h[j]此状态下水槽面积为 S(i,j) 。由于可容纳水的高度由两板中的 短板 决定因此可得如下 面积公式 S ( i , j ) m i n ( h [ i ] , h [ j ] ) × ( j − i ) S(i,j)min(h[i],h[j])×(j−i) S(i,j)min(h[i],h[j])×(j−i) 在每个状态下无论长板或短板向中间移动一次都会导致面积 底边宽度 −1 变短
如果向内 移动短板 水槽的短板 min(h[i],h[j]) 可能变大下个水槽的面积 可能会增大 。如果向内 移动长板 水槽的短板 min(h[i],h[j]) 不变或变小下个水槽的面积 一定会变小 。 所以初始化双指针为左右两端循环每轮将短板向内移动一次并更新面积最大值直到两指针相遇时跳出即可获得最大面积。
算法流程
初始化 双指针 i ,j 分列水槽左右两端循环收窄 直至双指针相遇时跳出 a. 更新面积最大值 res b. 选定两板高度中的短板向中间收窄一格返回值 返回面积最大值 res 即可
正确性证明 若暴力枚举水槽两板围成面积 S(i,j) 的状态总数为C(n,2) 。
假设状态 S(i,j)下 h[i]h[j] 在向内移动短板至S(i1,j)则相当于消去了 S(i,j−1),S(i,j−2),...,S(i,i1) 状态集合。而所有消去状态的面积一定都小于当前面积即S(i,j)因为这些状态
短板高度相比 S(i,j)相同或更短即 ≤h[i] 底边宽度相比 S(i,j) 更短 因此每轮向内移动短板所有消去的状态都 不会导致面积最大值丢失 复杂度分析 时间复杂度 O(N) 双指针遍历一次底边宽度 N 。 空间复杂度 O(1) 变量 i ,j , res 使用常数额外空间。
代码
#include stdio.h // 自定义max函数
int max(int a, int b) { return a b ? a : b;
} // 函数的参数是整数数组和数组的长度
int maxArea(int* height, int heightSize) { int i 0, j heightSize - 1, res 0; while(i j) { res (height[i] height[j]) ? max(res, (j - i) * height[i]): max(res, (j - i) * height[j--]); } return res;
} int main() { // 示例数组 int height[] {1, 8, 6, 2, 5, 4, 8, 3, 7}; int heightSize sizeof(height) / sizeof(height[0]); // 调用maxArea函数 int result maxArea(height, heightSize); // 输出结果 printf(The maximum area is: %d\n, result); return 0;
}代码思路来源作者Krahets
