前言
壁紙推薦
圖片著作小圣anx：https://bcy.net/item/detail/6885930410862189571?_source_page=cos
博主簡介
博主介紹：
– 本人是了凡，意義是希望本人任何時候以善良為先，以人品為重，喜歡了凡四訓中的立命之學、改過之法、積善之方、謙德之效四訓，更喜歡每日在簡書上投稿日更的讀書感悟筆名：三月_劉超，專注于 Go Web 后端，輔學Python、Java、演算法、前端等領域，未來大家一起加油啊~
文章目錄
- 前言
- 壁紙推薦
- 博主簡介
- 題目A：簡單
- 題目：移動零
- 示例:
- 題解：
- 題目B：中等
- 題目：盛最多水的容器
- 示例：
- 題解：
- 題目C：困難
- 題目：柱狀圖中最大的矩形
- 示例:
- 題解：
題目A：簡單
題目：移動零
給定一個陣列 nums，撰寫一個函式將所有 0 移動到陣列的末尾，同時保持非零元素的相對順序，
示例:
示例 1：
輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]
題解：
思路：雙指標解法
public class A{
public void moveZeroes(int[] nums) {
int l = 0, r = 0;
while (r < nums.length) {
if (nums[r] != 0) {
int t = nums[l];
nums[l] = nums[r];
nums[r] = t;
l++;
}
r++;
}
}
}
題目B：中等
題目：盛最多水的容器
給你 n 個非負整數 a1，a2，…，an，每個數代表坐標中的一個點 (i, ai) ，在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0) ，找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水，
說明：你不能傾斜容器，
示例：
示例 1：
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
解釋：圖中垂直線代表輸入陣列 [1,8,6,2,5,4,8,3,7]，在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49，
示例 2：
輸入：height = [1,1]
輸出：1
示例 3：
輸入：height = [4,3,2,1,4]
輸出：16
示例 4：
輸入：height = [1,2,1]
輸出：2
題解：
思路：雙指標寫法
class B{
public int maxArea(int[] height) {
int max = 0;
for(int i = 0, j = height.length - 1; i < j;){
int minHeight = height[i] < height[j] ? height[i ++] : height[j --];
int are = (j - i + 1) * minHeight;
max = Math.max(max, are);
}
return max;
}
}
題目C：困難
題目：柱狀圖中最大的矩形
給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度，每個柱子彼此相鄰，且寬度為 1 ，
求在該柱狀圖中，能夠勾勒出來的矩形的最大面積，
示例:
示例 1：
輸入: [2,1,5,6,2,3]
輸出: 10
題解：
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];
Stack<Integer> mono_stack = new Stack<Integer>();
for (int i = 0; i < n; ++i) {
while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
mono_stack.pop();
}
left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
mono_stack.push(i);
}
mono_stack.clear();
for (int i = n - 1; i >= 0; --i) {
while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
mono_stack.pop();
}
right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
mono_stack.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
后序每周持續更新！
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/287651.html
標籤：其他