min<\/em>(height[left],height[right]);
int size = tHeight*(right-left);
if (size>result){
result=size;
}
if (height[left]==tHeight){
left++;
}else{
right--;
}
}
return result;
}<\/code><\/pre>\n\n\n\n15.\u4e09\u6570\u4e4b\u548c<\/h1>\n\n\n\n
\u4e24\u79cd\u601d\u8def\uff1a<\/p>\n\n\n\n
1.\u53cc\u6307\u9488\uff08\u4e09\u6307\u9488\uff09\uff1a<\/h2>\n\n\n\n
\u56fa\u5b9a\u4e00\u4e2afirst\uff0c\u53e6\u5916\u4e24\u4e2a\u540c\u5411\u79fb\u52a8\uff0c\u9047\u5230\u91cd\u590d\u7684\u8fde\u7eed\u8df3\u8fc7\u3002<\/p>\n\n\n\n
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
\/\/\u5148\u6392\u5e8f\uff0c\u4f7f\u5f97\u53cc\u5411\u6307\u9488\u79fb\u52a8\u6709\u903b\u8f91\u3001\u5e76\u4e14\u53ef\u4ee5\u53bb\u91cd
Arrays.sort<\/em>(nums);
\/\/\u56fa\u5b9a\u4e00\u4e2afirst\uff0c\u53e6\u5916\u4e24\u4e2a\u540c\u5411\u79fb\u52a8\uff0c\u9047\u5230\u91cd\u590d\u7684\u8fde\u7eed\u8df3\u8fc7\u3002\u5f53first>0\u5c31\u627e\u4e0d\u5230\u4e86\u3002
for (int first = 0; first < nums.length - 2; first++) {
if (first > 0 && nums[first] == nums[first - 1]) continue;
if (nums[first] > 0) break;
int left = first + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[first] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList<\/em>(nums[first], nums[left], nums[right]));
left++;
right--;
\/\/\u53bb\u91cd
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (sum < 0) {
\/\/sum<0\u8bf4\u660e\u8981\u5f80\u5927\u8d70\uff0c\u5373left\u53f3\u79fb
left++;
\/\/\u53bb\u91cd
while (left < right && nums[left] == nums[left - 1]) left++;
} else {
\/\/\u5bf9\u79f0\u903b\u8f91
right--;
\/\/\u53bb\u91cd
while (left < right && nums[right] == nums[right + 1]) right--;
}
}
}
return result;
}<\/pre>\n\n\n\n2.\u56fa\u5b9a\u4e00\u4e2a\uff0c\u201c\u4e24\u6570\u4e4b\u548c\u201d<\/h2>\n\n\n\n
\u7528hash\u8868\u3002<\/p>\n\n\n\n
public static List<List<Integer>> threeSum(int[] nums) {\n List<List<Integer>> res = new ArrayList<>();\n Arrays.sort(nums); \/\/ \u6392\u5e8f\u662f\u4e3a\u4e86\u540e\u7eed\u53bb\u91cd\u65b9\u4fbf\n\n for (int i = 0; i < nums.length - 2; i++) {\n \/\/ \u8df3\u8fc7\u91cd\u590d a\n if (i > 0 && nums[i] == nums[i - 1]) continue;\n\n int target = -nums[i];\n Set<Integer> seen = new HashSet<>();\n for (int j = i + 1; j < nums.length; j++) {\n int complement = target - nums[j];\n if (seen.contains(complement)) {\n res.add(Arrays.asList(nums[i], complement, nums[j]));\n\n \/\/ \u8df3\u8fc7\u91cd\u590d b\n while (j + 1 < nums.length && nums[j] == nums[j + 1]) j++;\n }\n seen.add(nums[j]);\n }\n }\n\n return res;\n}\n<\/code><\/pre>\n\n\n\n\u53e6\u5916\uff0c\u300c\u56db\u6570\u4e4b\u548c\u300d\u300ck\u6570\u4e4b\u548c\u300d\u7b49\u95ee\u9898\u7684\u901a\u7528\u89e3\u6cd5<\/strong>\u5c31\u662f\u901a\u8fc7\u9012\u5f52\u5730\u5c06\u95ee\u9898\u8f6c\u5316\u4e3a\u201c\u4e24\u6570\u4e4b\u548c\u201d<\/strong>\u3002<\/p>\n\n\n\n42.\u63a5\u96e8\u6c34<\/h1>\n\n\n\npublic static int trap(int[] height) {
\/\/\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a O (n)\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6\u4e3a O (1)\u3002
int ans=0;
int left = 0;
int right = height.length-1;
int preMax = 0;
int sufMax = 0;
while (left<=right){
\/\/\u66f4\u65b0\u524d\u7f00\u6700\u5927\u503c\u548c\u540e\u7f00\u6700\u5927\u503c
preMax = Math.max<\/em>(height[left],preMax);
sufMax = Math.max<\/em>(height[right],sufMax);
\/\/\u5f53\u524d\u4f4d\u7f6e\u63a5\u6c34\u9ad8\u5ea6\u53d6\u51b3\u4e8e\u5de6\u53f3\u8fb9\u754c\u4e2d\u8f83\u5c0f\u7684\u503c
if (preMax<sufMax){
\/\/\u5982\u679c\u5f53\u524d\u524d\u7f00\u6700\u5927\u503c\u5c0f\u4e8e\u540e\u7f00\u6700\u5927\u503c\uff0c\u90a3\u4e48\u524d\u7f00\u6700\u5927\u503c\u5c31\u662f\u8981\u6c42\u7684\u201c\u8f83\u5c0f\u7684\u503c\u201d\uff0c\u56e0\u4e3a\u540e\u7f00\u6700\u5927\u503c\u4e0d\u80fd\u66f4\u5c0f\u4e86\u3002
ans+=preMax-height[left];
left++;
}else {
\/\/\u540c\u7406\u5bf9\u79f0\uff0c\u6b64\u5904\u5305\u542b\u76f8\u7b49\u7684\u903b\u8f91\uff0c\u76f8\u7b49\u65f6\u8c01\u51cf\u5e95\u5ea7\u90fd\u4e00\u6837\u3002
ans+=sufMax-height[right];
right--;
}
}
return ans;
}<\/pre>\n","protected":false},"excerpt":{"rendered":"\u53cc\u6307\u9488\u5e38\u89c1\u7684\u4e09\u5927\u7c7b\u7528\u6cd5\uff1a \u5176\u5b9e\u53cc\u6307\u9488\u53ef\u4ee5\u5f52\u4e3a \u4e09\u7c7b\u7b56\u7565\uff0c\u5206\u522b\u662f\uff1a 1. \u5bf9\u649e\u6307\u9488\uff08Two Pointers f […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[75],"class_list":["post-851","post","type-post","status-publish","format-standard","hentry","category-3","tag-75"],"_links":{"self":[{"href":"http:\/\/www.cmd137blog.top\/index.php?rest_route=\/wp\/v2\/posts\/851","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.cmd137blog.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.cmd137blog.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.cmd137blog.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.cmd137blog.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=851"}],"version-history":[{"count":8,"href":"http:\/\/www.cmd137blog.top\/index.php?rest_route=\/wp\/v2\/posts\/851\/revisions"}],"predecessor-version":[{"id":1087,"href":"http:\/\/www.cmd137blog.top\/index.php?rest_route=\/wp\/v2\/posts\/851\/revisions\/1087"}],"wp:attachment":[{"href":"http:\/\/www.cmd137blog.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=851"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.cmd137blog.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=851"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.cmd137blog.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=851"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}