單調(diào)棧

# LeetCode

[LeetCode - 兩數(shù)之和](bear://x-callback-url/open-note?id=528FA01A-F991-4A76-96D1-D8A2068DC153-417-0000006E18FCA84C&header=%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C)

[LeetCode - 兩個(gè)鏈表相加](bear://x-callback-url/open-note?id=528FA01A-F991-4A76-96D1-D8A2068DC153-417-0000006E18FCA84C&header=%E4%B8%A4%E4%B8%AA%E9%93%BE%E8%A1%A8%E7%9B%B8%E5%8A%A0)

[LeetCode - 無(wú)重復(fù)字符的最長(zhǎng)子串](bear://x-callback-url/open-note?id=528FA01A-F991-4A76-96D1-D8A2068DC153-417-0000006E18FCA84C&header=%E6%97%A0%E9%87%8D%E5%A4%8D%E5%AD%97%E7%AC%A6%E7%9A%84%E6%9C%80%E9%95%BF%E5%AD%90%E4%B8%B2)

[LeetCode - 三數(shù)之和](bear://x-callback-url/open-note?id=528FA01A-F991-4A76-96D1-D8A2068DC153-417-0000006E18FCA84C&header=%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C)

[LeetCode - 爬樓梯](bear://x-callback-url/open-note?id=528FA01A-F991-4A76-96D1-D8A2068DC153-417-0000006E18FCA84C&header=%E7%88%AC%E6%A5%BC%E6%A2%AF)

[LeetCode - k個(gè)一組翻轉(zhuǎn)鏈表](bear://x-callback-url/open-note?id=528FA01A-F991-4A76-96D1-D8A2068DC153-417-0000006E18FCA84C&header=k%E4%B8%AA%E4%B8%80%E7%BB%84%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8)

[LeetCode - 接雨水](bear://x-callback-url/open-note?id=528FA01A-F991-4A76-96D1-D8A2068DC153-417-0000006E18FCA84C&header=%E6%8E%A5%E9%9B%A8%E6%B0%B4)

[LeetCode - 環(huán)形鏈表及相遇問(wèn)題](bear://x-callback-url/open-note?id=528FA01A-F991-4A76-96D1-D8A2068DC153-417-0000006E18FCA84C&header=%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8%E5%8F%8A%E7%9B%B8%E9%81%87%E9%97%AE%E9%A2%98)

[LeetCode - 整數(shù)翻轉(zhuǎn)](bear://x-callback-url/open-note?id=528FA01A-F991-4A76-96D1-D8A2068DC153-417-0000006E18FCA84C&header=%E6%95%B4%E6%95%B0%E7%BF%BB%E8%BD%AC)

[LeetCode - 最小棧](bear://x-callback-url/open-note?id=528FA01A-F991-4A76-96D1-D8A2068DC153-417-0000006E18FCA84C&header=%E6%9C%80%E5%B0%8F%E6%A0%88)

# 兩數(shù)之和

把所有元素存入hash表中，再通過(guò)遍歷數(shù)組，目標(biāo)值減去數(shù)組中的元素與hash表查找，如果有，則返回（邊存邊遍歷）

```java

哈希表

class Solution

? ? public int[] twoSum(int[] arr, int target){

? ? ? ? int[] res = new int[2];

? ? ? ? HashMap map = new HashMap<Integer,Integer>();

? ? ? ? for (int i = 0; i < arr.length; i++) {

? ? ? ? ? ? if (map.containsKey(arr[i])){

? ? ? ? ? ? ? ? res[0] = i;

? ? ? ? ? ? ? ? res[1] = (int) map.get(arr[i]);

? ? ? ? ? ? ? ? return res;

? ? ? ? ? ? }

? ? ? ? ? ? map.put(target - arr[i],i);//值，下標(biāo)

? ? ? ? }

? ? ? ? return res;

? ? }

}

暴力法

public int[] twoSum2(int[] arr, int target){

? ? int[] res = new int[2];

? ? for (int i = 0; i < arr.length; i++) {

? ? ? ? for (int j = i + 1; j < arr.length; j++) {

? ? ? ? ? ? if (arr[i] + arr[j] == target){

? ? ? ? ? ? ? ? res[0] = i;

? ? ? ? ? ? ? ? res[0] = j;

? ? ? ? ? ? ? ? return res;

? ? ? ? ? ? }

? ? ? ? }

? ? }

? ? return res;

}

```

# 兩個(gè)鏈表相加

New 一個(gè)新鏈表，注意進(jìn)位還需要加1

```java

class Solution {

? ? public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

? ? ? ? int sum = 0;

? ? ? ? int j = 0;

? ? ? ? int y = 0;

? ? ? ? ListNode head = new ListNode(0);//頭結(jié)點(diǎn)

? ? ? ? ListNode cur = head;//指針

? ? ? ? while(l1 != null || l2 != null || j != 0){//有多出來(lái)的進(jìn)

? ? ? ? ? ? int v1 = l1 != null ? l1.val : 0;//鏈表中的值

? ? ? ? ? ? int v2 = l2 != null ? l2.val : 0;

? ? ? ? ? ? sum = v1 + v2 + j;

? ? ? ? ? ? j = sum / 10;

? ? ? ? ? ? y = sum % 10;

? ? ? ? ? ? ListNode node = new ListNode(y);//new 一個(gè)節(jié)點(diǎn)

? ? ? ? ? ? cur.next = node;//接到頭節(jié)點(diǎn)里面

? ? ? ? ? ? cur = cur.next;//下一個(gè)節(jié)點(diǎn)

? ? ? ? ? ? l1 = l1 != null ? l1.next : null;

? ? ? ? ? ? l2 = l2 != null ? l2.next : null;

? ? ? ? }

? ? ? ? return head.next;

? ? }

}

```

# 無(wú)重復(fù)字符的最長(zhǎng)子串

滑動(dòng)窗口，控制左右指針移動(dòng)，右指針包含左指針，先右指針后判斷是否需要左指針，每一輪右指針循環(huán)時(shí)更新最長(zhǎng)的子串。

兩個(gè)while ，一個(gè)右一個(gè)左，先移動(dòng)右再移動(dòng)左，左在右里面移動(dòng)

```

class Solution {

? ? ? ? public int lengthOfLongestSubstring(String s) {

? ? ? ? int left = 0;

? ? ? ? int right = 0;

? ? ? ? int res = 0;

? ? ? ? int[] arr = new int[128];//每一個(gè)字符對(duì)應(yīng)的編碼數(shù)字，128之內(nèi)

? ? ? ? while (right < s.length()){

? ? ? ? ? ? char c = s.charAt(right);//一開(kāi)始循環(huán)的右指針

? ? ? ? ? ? right++;

? ? ? ? ? ? arr[c]++;

? ? ? ? ? ? while (arr[c] > 1){//如果已經(jīng)有過(guò)這個(gè)字符了就從左開(kāi)始刪除，直到刪除了之前添加的數(shù)

? ? ? ? ? ? ? ? char l = s.charAt(left);//窗口往左移，直到

? ? ? ? ? ? ? ? left++;

? ? ? ? ? ? ? ? arr[l]--;

? ? ? ? ? ? }

? ? ? ? ? ? res = Math.max(res,right - left);//拿到最長(zhǎng)的子串

? ? ? ? }

? ? ? ? return res;

? ? }

}

```

# 三數(shù)之和

一個(gè)外層的for循環(huán)，for循環(huán)里面用雙指針指向循環(huán)的開(kāi)始和結(jié)尾處，左指針為i+1i+1，右邊為最末位

當(dāng)判斷 sum == 0 時(shí)，分別移動(dòng)雙指針，使其試圖找到多個(gè)結(jié)果，并做去重判斷

大于0 右指針左移

小于0 左指針右移

Arrays.sort(int[])// 排序

```java

class Solution {

? ? public List<List<Integer>> threeSum(int[] nums){

? ? ? ? List res = new ArrayList<List<Integer>>();

? ? ? ? int len = nums.length;

? ? ? ? Arrays.sort(nums);

? ? ? ? if (nums == null || len < 3){

? ? ? ? ? ? return res;

? ? ? ? }

? ? ? ? for (int i = 0; i < len; i++) {//最外層for循環(huán)，O（N）

? ? ? ? ? ? int left = i + 1;

? ? ? ? ? ? int right = len - 1;

? ? ? ? ? ? int sum;

? ? ? ? ? ? if (nums[i] > 0) break;//如果這個(gè)數(shù)大于0了，退出

? ? ? ? ? ? if (i > 0 && nums[i - 1] == nums[i]) continue;//for循環(huán)的去重

? ? ? ? ? ? while (left < right){//雙指針開(kāi)始

? ? ? ? ? ? ? ? sum = nums[i] + nums[left] + nums[right];//和的大小于0

? ? ? ? ? ? ? ? if (sum == 0){//分別與0比較

? ? ? ? ? ? ? ? ? ? res.add(Arrays.asList(nums[i],nums[left],nums[right]));//加入列表中

? ? ? ? ? ? ? ? ? ? while (left < right && nums[right] == nums[right - 1]) right--;//去重

? ? ? ? ? ? ? ? ? ? while (left < right && nums[left] == nums[left + 1]) left--;

? ? ? ? ? ? ? ? ? ? right--;

? ? ? ? ? ? ? ? ? ? left++;

? ? ? ? ? ? ? ? }else if (sum > 0) right--;

? ? ? ? ? ? ? ? else if (sum < 0)left++;

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return res;

? ? }

}

```

# 爬樓梯

```

O（N），O(1)自下而上

? ? public int climbStairs(int num){

? ? ? ? int sum = 0;

? ? ? ? int a = 1;

? ? ? ? int b = 2;

? ? ? ? if(num < 3) return num;

? ? ? ? for (int i = 3; i <= num; i++) {

? ? ? ? ? ? sum = a + b;

? ? ? ? ? ? a = b;

? ? ? ? ? ? b = sum;

? ? ? ? }

? ? ? ? return sum;

? ? }

dp數(shù)組，自下而上

? ? ? ? public int climbStairs(int num){

? ? ? ? int[] dp = new int[num + 1];

? ? ? ? if (num < 3) return num;

? ? ? ? dp[1] = 1;

? ? ? ? dp[2] = 2;

? ? ? ? for (int i = 3; i < num + 1; i++) {

? ? ? ? ? ? if(dp[i] != 0) return dp[i];

? ? ? ? ? ? dp[i] = dp[i - 1] + dp[i - 2];

? ? ? ? }

? ? ? ? return dp[num];

? ? }

```

# k個(gè)一組翻轉(zhuǎn)鏈表

*### 解題思路*

翻轉(zhuǎn)鏈表的思路：

1、拿到下一個(gè)節(jié)點(diǎn)的值防止丟失，后面要用

2、翻轉(zhuǎn)指針

3、指針右移

4、取出下一個(gè)節(jié)點(diǎn)的值，（指針右移）

K個(gè)鏈表思路：

構(gòu)造一個(gè)頭指針，連接原來(lái)的頭指針

K個(gè)節(jié)點(diǎn)，使用for循環(huán)走到第k個(gè)值，退出循環(huán)，指針指向第k個(gè)值end

構(gòu)造一個(gè)前驅(qū)指針，一個(gè)末尾指針

構(gòu)造一個(gè)頭指針，一個(gè)下一個(gè)k次循環(huán)節(jié)點(diǎn)的頭，防止丟失

隔斷每k個(gè)鏈表，末尾為null

翻轉(zhuǎn)鏈表

指針為下一次的指向移動(dòng)

連接其他組的鏈表

前驅(qū)指針為上次的末尾指針，也就是start

Prepre 和 end 指針一起，（下一組由 end 移動(dòng)找k個(gè)節(jié)點(diǎn)）

*### 代碼*

```java

class Solution {

? ? public ListNode reverseKGroup(ListNode head, int k){

? ? ? ? ListNode dummy = new ListNode(0);

? ? ? ? dummy.next = head;

? ? ? ? ListNode pre = dummy;//前驅(qū)

? ? ? ? ListNode end = dummy;//末尾

? ? ? ? while (end.next != null){

? ? ? ? ? ? for (int i = 0; i < k && end != null; i++) {

? ? ? ? ? ? ? ? end = end.next;

? ? ? ? ? ? }//找到第k個(gè)

? ? ? ? ? ? if (end == null) break;

? ? ? ? ? ? ListNode start = pre.next;//需要翻轉(zhuǎn)的頭

? ? ? ? ? ? ListNode tail = end.next;//保存下個(gè)k節(jié)點(diǎn)的頭

? ? ? ? ? ? end.next = null;//開(kāi)始翻轉(zhuǎn)

? ? ? ? ? ? pre.next = revers(start);//返回的是末尾的節(jié)點(diǎn)，接到前驅(qū)節(jié)點(diǎn)

? ? ? ? ? ? start.next = tail;//此時(shí)的start在尾部，連接下個(gè)k節(jié)點(diǎn)的頭

? ? ? ? ? ? pre = start;//再次記錄前驅(qū)節(jié)點(diǎn)

? ? ? ? ? ? end = pre;//pre跟end走一起，由end往下走到第k個(gè)節(jié)點(diǎn)

? ? ? ? }

? ? ? ? return dummy.next;

? ? }

? ? public ListNode revers(ListNode head){

? ? ? ? ListNode pre = null;

? ? ? ? ListNode cur = head;

? ? ? ? while (cur != null){

? ? ? ? ? ? ListNode next = cur.next;//拿到后面的值不然它丟失

? ? ? ? ? ? cur.next = pre;//翻轉(zhuǎn)鏈表

? ? ? ? ? ? pre = cur;//指針右移

? ? ? ? ? ? cur = next;//指針右移,取后面的值

? ? ? ? }

? ? ? ? return pre;

? ? }

}

```

# 接雨水

兩邊的較小值減去該處的值得到該出的雨水量

```java

//暴力法

public int trap(int[] num){

? ? int sum = 0;

? ? for (int i = 1; i < num.length - 1; i++) {

? ? ? ? int left_max = 0; int right_max = 0;//每一次循環(huán)都需要初始化

? ? ? ? for (int j = i; j < num.length; j++) {//向右

? ? ? ? ? ? left_max = Math.max(left_max, num[j]);//左邊的最大高度

? ? ? ? }

? ? ? ? for (int j = i; j >= 0 ; j--) {//向左

? ? ? ? ? ? right_max = Math.max(right_max, num[j]);//右邊的最大高度

? ? ? ? }//找到兩邊的最大值后計(jì)算雨水

? ? ? ? sum += Math.min(left_max, right_max) - num[i];//兩邊的較小值減去該處的值得到該出的雨水量

? ? }

? ? return sum;

}

//雙指針?lè)?/p>

public int trap3(int[] num){

? ? int n = num.length;

? ? int sum = 0;

? ? int left = 0;

? ? int right = n - 1;

? ? int left_max = 0;

? ? int right_max = 0;

? ? while (left < right){

? ? ? ? if (num[left] < num[right]){//決定權(quán)在小的一邊

? ? ? ? ? ? if (num[left] >= left_max){

? ? ? ? ? ? ? ? left_max = num[left];//單調(diào)遞增，左邊無(wú)法儲(chǔ)水

? ? ? ? ? ? }else{

? ? ? ? ? ? ? ? sum += (left_max - num[left]);

? ? ? ? ? ? }

? ? ? ? ? ? ++left;

? ? ? ? } else{

? ? ? ? ? ? if (num[right] >= right_max){

? ? ? ? ? ? ? ? right_max = num[right];//往左單調(diào)遞增右邊無(wú)法儲(chǔ)水

? ? ? ? ? ? }else{

? ? ? ? ? ? ? ? sum += (right_max - num[right]);

? ? ? ? ? ? }

? ? ? ? ? ? --right;

? ? ? ? }

? ? }

? ? return sum;

}

//單調(diào)棧

public int trap4(int[] nums) {

? ? Stack<Integer> stack = new Stack<>();

? ? int sum = 0;

? ? int n = nums.length;

? ? for (int i = 0; i < n; i++) {

? ? ? ? while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]){//構(gòu)造單調(diào)棧，遞減

? ? ? ? ? ? int res = stack.pop();//彈出的是第幾個(gè)數(shù)

? ? ? ? ? ? if (!stack.isEmpty()) {

? ? ? ? ? ? ? ? //高 * 長(zhǎng)? 兩邊的較小值減去該處的值得到該出的雨水量（高），從棧里面彈出的為長(zhǎng)

? ? ? ? ? ? ? ? sum += (Math.min(nums[i], nums[stack.peek()]) - nums[res]) * (i - stack.peek() - 1);

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? stack.push(i);

? ? }

? ? return sum;

}

//dp數(shù)組

public int trap2(int[] num){

? ? int[][] dp = new int[num.length][2];//定義dp數(shù)組

? ? int sum = 0;

? ? //base case

? ? dp[0][0] = num[0];//設(shè)為最左邊，默認(rèn)

? ? dp[num.length - 1][1] = num[num.length - 1];//假設(shè)為最右邊

? ? for (int j = 1; j < num.length; j++) {//最左最右邊的不要

? ? ? ? dp[j][0] = Math.max(dp[j - 1][0], num[j]);//左

? ? }

? ? for (int j = num.length - 2; j >= 0; j--) {//最左最右邊的不要

? ? ? ? dp[j][1] = Math.max(dp[j + 1][1], num[j]);//不過(guò)dp數(shù)組需要包含最左最右

? ? }

? ? for (int j = 1; j < num.length - 1; j++) {

? ? ? ? sum += Math.min(dp[j][0], dp[j][1]) - num[j];

? ? }

? ? return sum;

}

```

# 環(huán)形鏈表及相遇問(wèn)題

```java

public class LinkedCycle {

? ? //快慢指針判斷是否是環(huán)形鏈表

? ? public Node hasCycle(Node head){

? ? ? ? Node fast = head;

? ? ? ? Node slow = head;

? ? ? ? while (fast != null && fast.next != null){//倒數(shù)第二個(gè)

? ? ? ? ? ? fast = fast.next.next;

? ? ? ? ? ? slow = slow.next;

? ? ? ? ? ? if (fast == slow) return fast;//相遇點(diǎn) true；

? ? ? ? }

? ? ? ? return head;//沒(méi)有相遇 false；

? ? }


? ? //找到環(huán)的頭結(jié)點(diǎn)

? ? public Node detectCycle(Node head){

? ? ? ? Node node = hasCycle(head);//相遇的節(jié)點(diǎn)

? ? ? ? Node cur = head;//頭結(jié)點(diǎn)

? ? ? ? while (cur != node){//兩個(gè)指針一起一步步走，一定在環(huán)形入口處相遇，步數(shù)為：K-W

? ? ? ? ? ? node = node.next;

? ? ? ? ? ? cur = cur.next;

? ? ? ? }

? ? ? ? return cur;

? ? }

```

# 整數(shù)翻轉(zhuǎn)

```java

class Solution {

? ? public int reverse(int x) {

? ? ? ? int res = 0;

? ? ? ? while(x != 0){

? ? ? ? ? ? int tmp = res;//保留翻轉(zhuǎn)前的數(shù)字，為后面的判斷做準(zhǔn)備

? ? ? ? ? ? res = tmp * 10 +? x % 10;//取余

? ? ? ? ? ? x = x / 10;//下次翻轉(zhuǎn)

? ? ? ? ? ? if(tmp != res / 10) return 0;//一旦發(fā)現(xiàn)翻轉(zhuǎn)后與翻轉(zhuǎn)前發(fā)生不可預(yù)知的變化返回0

? ? ? ? }

? ? ? ? return res;

? ? }

}

```

# 最小棧

必須在構(gòu)建的時(shí)候把最小值拿到手，否則后面計(jì)算費(fèi)時(shí)間費(fèi)空間

```java

public class MinStack {

? ? LinkedList<Integer> zstack;

? ? LinkedList<Integer> fstack;

? ? MinStack(){

? ? ? ? zstack = new LinkedList<>();

? ? ? ? fstack = new LinkedList<>();

? ? ? ? fstack.push(Integer.MAX_VALUE);

? ? }

? ? public void push(int val){

? ? ? ? zstack.push(val);

? ? ? ? fstack.push(Math.min(fstack.peek(),val));

? ? }

? ? public void pop(){

? ? ? ? zstack.pop();

? ? ? ? fstack.pop();

? ? }

? ? public int top(){

? ? ? ? return zstack.peek();

? ? }

? ? public int getMin(){

? ? ? ? return fstack.peek();

? ? }

}

//無(wú)需輔助棧

public void push(int x) {

? ? ? ? if(min >= x){

? ? ? ? ? ? stack.push(min);//上一次的最小值

? ? ? ? ? ? min = x;

? ? ? ? }

? ? ? ? stack.push(x);

? ? }

? ? public void pop() {

//彈出，如果彈出的是最小值，繼續(xù)彈出一次

? ? ? ? if(stack.pop() == min){? ? ? ? ? ?

min = stack.pop();//彈出第二次，上次的最小值

? ? ? ? }

? ? }

```

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀(guān)點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 技術(shù)交流QQ群:1027579432，歡迎你的加入！ 歡迎關(guān)注我的微信公眾號(hào)：CurryCoder的程序人生 1....
    CurryCoder閱讀 2,017評(píng)論 0贊 2
  • <center>#1 Two Sum</center> link Description:Given an arr...
    鐺鐺鐺clark閱讀 2,355評(píng)論 0贊 3
  • ● 如何打印二叉樹(shù)每層的節(jié)點(diǎn)？ 考察點(diǎn)：二叉樹(shù) 參考回答： 實(shí)現(xiàn)代碼： import java.util.Arra...
    le_u閱讀 615評(píng)論 0贊 0
  • 劍指Offer系列 [TOC] 數(shù)組和字符串 劍指offer 04.二維數(shù)組中的查找 從左下角開(kāi)始查找，二分思想。...
    SwiftGo閱讀 505評(píng)論 0贊 1
  • <center>#104 Maximum Depth of Binary Tree</center> link D...
    鐺鐺鐺clark閱讀 1,693評(píng)論 0贊 0

友情鏈接更多精彩內(nèi)容