【LeetCode熱題100】打卡第39天：數(shù)組中第K個(gè)最大元素&最大正方形

?前言

大家好，我是知識(shí)汲取者，歡迎來(lái)到我的LeetCode熱題100刷題專欄！

精選 100 道力扣（LeetCode）上最熱門(mén)的題目，適合初識(shí)算法與數(shù)據(jù)結(jié)構(gòu)的新手和想要在短時(shí)間內(nèi)高效提升的人，熟練掌握這 100 道題，你就已經(jīng)具備了在代碼世界通行的基本能力。在此專欄中，我們將會(huì)涵蓋各種類(lèi)型的算法題目，包括但不限于數(shù)組、鏈表、樹(shù)、字典樹(shù)、圖、排序、搜索、動(dòng)態(tài)規(guī)劃等等，并會(huì)提供詳細(xì)的解題思路以及Java代碼實(shí)現(xiàn)。如果你也想刷題，不斷提升自己，就請(qǐng)加入我們吧！QQ群號(hào)：827302436。我們共同監(jiān)督打卡，一起學(xué)習(xí)，一起進(jìn)步。

博客主頁(yè)??：知識(shí)汲取者的博客

LeetCode熱題100專欄??：LeetCode熱題100

Gitee地址??：知識(shí)汲取者 (aghp) - Gitee.com

題目來(lái)源??：LeetCode 熱題 100 - 學(xué)習(xí)計(jì)劃 - 力扣（LeetCode）全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)

PS：作者水平有限，如有錯(cuò)誤或描述不當(dāng)?shù)牡胤?，懇?qǐng)及時(shí)告訴作者，作者將不勝感激

數(shù)組中的第K個(gè)最大元素

??題目

原題鏈接：215.數(shù)組中的第K個(gè)最大元素

??題解

• 解法一：使用快速排序API

  import java.util.Arrays;
  import java.util.Collections;
  
  /**
   * @author ghp
   * @title
   * @description
   */
  class Solution {
      public int findKthLargest(int[] nums, int k) {
          Integer[] arr = Arrays.stream(nums).boxed().toArray(Integer[]::new);
          Arrays.sort(arr, Collections.reverseOrder());
          return arr[k - 1];
      }
  }
  

  復(fù)雜度分析：

  • 時(shí)間復(fù)雜度：最壞$O(n^2)$，最好$O(1)$
  • 空間復(fù)雜度：$O(n)$，arr占用空間n，快排遞歸占用空間 logn，所以總的空間復(fù)雜度為 n

  其中 $n$ 為數(shù)組中元素的個(gè)數(shù)

  代碼優(yōu)化：

  class Solution {
      public int findKthLargest(int[] nums, int k) {
          Arrays.sort(nums);
          return nums[nums.length - k];
      }
  }
  

  復(fù)雜度分析：

  • 時(shí)間復(fù)雜度：最壞$O(n^2)$，最好$O(1)$
  • 空間復(fù)雜度：$O(logn)$

  其中 $n$ 為數(shù)組中元素的個(gè)數(shù)

• 解法二：手動(dòng)實(shí)現(xiàn)快速排序

  /**
   * @author ghp
   * @title
   * @description
   */
  class Solution {
      public int findKthLargest(int[] nums, int k) {
          return findKthLargestByQuickSort(nums, 0, nums.length - 1, k);
      }
  
      private int findKthLargestByQuickSort(int[] nums, int left, int right, int k) {
          if (left > right) {
              // 區(qū)間中沒(méi)有元素，無(wú)法繼續(xù)劃分區(qū)間（根據(jù)題意，這里永不可達(dá)）
              return -1;
          }
          // 隨機(jī)化選取主元
          int pivot = partition(nums, left, right);
          int result;
          if (k == pivot + 1) {
              // 第K大的元素是當(dāng)前主元
              result = nums[pivot];
          } else if (k < pivot  + 1) {
              // 第K大的元素在主元左側(cè)
              result = findKthLargestByQuickSort(nums, left, pivot - 1, k);
          } else {
              // 第K大的元素在主元右側(cè)
              result = findKthLargestByQuickSort(nums, pivot + 1, right, k);
          }
          // 劃分右側(cè)子區(qū)間
          return result;
      }
  
      private int partition(int[] nums, int left, int right) {
          int pivot = nums[right];
          int i = left - 1;
          // 根據(jù)主元將數(shù)組劃分為左右子數(shù)組（左側(cè)子數(shù)組>主元，右側(cè)子數(shù)組<=主元）
          for (int j = left; j < right; j++) {
              if (nums[j] > pivot) {
                  // 將比主元大的元素放到 i+1 的左側(cè)
                  swap(nums, ++i, j);
              }
          }
          // 將主元放到分界點(diǎn)，然后返回主元索引
          swap(nums, ++i, right);
          return i;
      }
  
      private void swap(int[] nums, int i, int j) {
          int temp = nums[i];
          nums[i] = nums[j];
          nums[j] = temp;
      }
  }
  

  復(fù)雜度分析：

  • 時(shí)間復(fù)雜度：最壞$O(n^2)$，最好$O(1)$
  • 空間復(fù)雜度：$O(logn)$

  其中 $n$ 為數(shù)組中元素的個(gè)數(shù)

  代碼優(yōu)化：時(shí)間復(fù)雜度優(yōu)化

  由于快速排序是不穩(wěn)定的，最好的情況$O(1)$，最壞的情況是$O(n^2)$，為了提高快排的穩(wěn)定性，我們可以引入一個(gè)隨機(jī)因子，使得時(shí)間復(fù)雜度的期望值接近于$O(n)$，這個(gè)快排是最基本的算法，這里不做過(guò)多介紹了，感興趣的可以參考我的另一篇文章：詳解十大排序算法，這篇文章詳細(xì)介紹了 十大排序算法的思路、實(shí)現(xiàn)，還有十分詳細(xì)的圖解

  import java.util.Random;
  
  /**
   * @author ghp
   * @title
   * @description
   */
  class Solution {
      public int findKthLargest(int[] nums, int k) {
          return findKthLargestByQuickSort(nums, 0, nums.length - 1, k);
      }
  
      private int findKthLargestByQuickSort(int[] nums, int left, int right, int k) {
          if (left > right) {
              // 區(qū)間中沒(méi)有元素，無(wú)法繼續(xù)劃分區(qū)間（根據(jù)題意，這里永不可達(dá)）
              return -1;
          }
          // 隨機(jī)化選取主元
          int pivot = randomPartition(nums, left, right);
          int result;
          if (k == pivot + 1) {
              // 第K大的元素是當(dāng)前主元
              result = nums[pivot];
          } else if (k < pivot + 1) {
              // 第K大的元素在主元左側(cè)
              result = findKthLargestByQuickSort(nums, left, pivot - 1, k);
          } else {
              // 第K大的元素在主元右側(cè)
              result = findKthLargestByQuickSort(nums, pivot + 1, right, k);
          }
          // 劃分右側(cè)子區(qū)間
          return result;
      }
  
      private int randomPartition(int[] nums, int left, int right) {
          // 從子區(qū)間中隨機(jī)選取一個(gè)元素作為主元
          Random random = new Random();
          int nonce = random.nextInt(right - left + 1) + left;
          swap(nums, nonce, right);
          int pivot = nums[right];
          int i = left - 1;
          // 根據(jù)主元將數(shù)組劃分為左右子數(shù)組（左側(cè)子數(shù)組>主元，右側(cè)子數(shù)組<=主元）
          for (int j = left; j < right; j++) {
              if (nums[j] > pivot) {
                  // 將比主元大的元素放到 i+1 的左側(cè)
                  swap(nums, ++i, j);
              }
          }
          // 將主元放到分界點(diǎn)，然后返回主元索引
          swap(nums, ++i, right);
          return i;
      }
  
      private void swap(int[] nums, int i, int j) {
          int temp = nums[i];
          nums[i] = nums[j];
          nums[j] = temp;
      }
  }
  

  復(fù)雜度分析：

  • 時(shí)間復(fù)雜度：$O(n)$
  • 空間復(fù)雜度：$O(logn)$

  其中 $n$ 為數(shù)組中元素的個(gè)數(shù)

• 解法三：堆排序

最大正方形

??題目

原題鏈接：221.最大正方形

??題解

• 解法一：向下擴(kuò)展

  本題思路可以參考這題：【LeetCode熱題100】打卡第26天：最大矩形

  兩者是類(lèi)似的題目，這題相較于 最大矩形 哪一題多了一個(gè)限制，那就是長(zhǎng)要等于寬。這里就不多做講解了 (●ˇ?ˇ●)

  PS：我感覺(jué)很離譜，前面那一題比這一題限制要少，但卻是困難提，這一題限制多反而是中等題，不知道LeetCode是怎么劃分題目難度的，我表示很疑惑??

  

  

  /**
   * @author ghp
   * @title
   * @description
   */
  class Solution {
      public int maximalSquare(char[][] matrix) {
          int row = matrix.length;
          int col = matrix[0].length;
          // 構(gòu)建width數(shù)組
          int[][] sum = new int[row][col];
          for (int i = 0; i < row; i++) {
              for (int j = 0; j < col; j++) {
                  if (matrix[i][j] == '1') {
                      if (j == 0) {
                          sum[i][j] = 1;
                      } else {
                          sum[i][j] += sum[i][j - 1] + 1;
                      }
                  } else {
                      sum[i][j] = 0;
                  }
              }
          }
          int ans = 0;
          // 枚舉每一個(gè)節(jié)點(diǎn)
          for (int i = 0; i < row; i++) {
              for (int j = 0; j < col; j++) {
                  int width = sum[i][j];
                  // 枚舉當(dāng)前節(jié)點(diǎn)下的所有行
                  for (int k = i; k < row; k++) {
                      int height = k - i + 1;
                      if (sum[k][j] < height || height > width) {
                          // 出現(xiàn)斷層 || 高已經(jīng)超過(guò)當(dāng)前寬度
                          break;
                      }
                      // 更新正方形的寬（正方形的面積受限于當(dāng)前已遍歷層中的最小寬）
                      width = Math.min(width, sum[k][j]);
                      // 更新最大矩形的面積（正方形的面積受限于長(zhǎng)和寬）
                      int t = Math.min(width, height);
                      ans = Math.max(ans, t * t);
                  }
              }
          }
          return ans;
      }
  }
  

  復(fù)雜度分析：

  • 時(shí)間復(fù)雜度：$O(n^2?m)$
  • 空間復(fù)雜度：$O(n?m)$

  其中 $n$ 為數(shù)組的行，$m$為數(shù)組的列

  可以看到，時(shí)間復(fù)雜度雖然比較高，但是卻能過(guò)，這是因?yàn)槲覀兺ㄟ^(guò)if (sum[k][j] < height || height > width)提前剔除了大量不必要的計(jì)算（起到了類(lèi)似于剪枝的效果），從而使得加速計(jì)算出結(jié)果

• 解法二：往上擴(kuò)展

  解法一，自上而下枚舉，節(jié)點(diǎn)要枚舉兩遍，第一遍枚舉構(gòu)建sum數(shù)組，第二遍枚舉計(jì)算節(jié)點(diǎn)能構(gòu)成矩形的最大面積。我們可以換一種思路，自下而上枚舉，在枚舉節(jié)點(diǎn)構(gòu)建sum數(shù)組的同時(shí)，還計(jì)算當(dāng)前節(jié)點(diǎn)能構(gòu)成矩形的最大面積，這樣就能夠省掉一遍枚舉，雖然時(shí)間復(fù)雜度沒(méi)有減小，但是節(jié)約了時(shí)間??

  PS：同樣的，也是參考之前最大矩形這題寫(xiě)的，不是很理解的可以回看，前面最大矩形那一題進(jìn)行了詳細(xì)的詳解，有圖有分析，可以說(shuō)是手把手教學(xué)

  /**
   * @author ghp
   * @title
   * @description
   */
  class Solution {
      public int maximalSquare(char[][] matrix) {
          int row = matrix.length;
          int col = matrix[0].length;
          int[][] sum = new int[row][col];
          int ans = 0;
          for (int i = 0; i < row; i++) {
              // 構(gòu)建sum數(shù)組
              for (int j = 0; j < col; j++) {
                  if (matrix[i][j] == '1') {
                      if (j == 0) {
                          sum[i][j] = 1;
                      } else {
                          sum[i][j] += sum[i][j - 1] + 1;
                      }
                  } else {
                      sum[i][j] = 0;
                  }
                  int width = sum[i][j];
                  // 以當(dāng)前節(jié)點(diǎn)為矩形的右下角，往上枚舉
                  for (int k = i; k >= 0; k--) {
                      int height = i - k + 1;
                      if (sum[k][j] < height || height > width) {
                          // 出現(xiàn)斷層 || 高已經(jīng)超過(guò)當(dāng)前寬度
                          break;
                      }
                      // 更新正方形的寬（正方形的面積受限于當(dāng)前已遍歷層中的最小寬）
                      width = Math.min(width, sum[k][j]);
                      // 更新最大矩形的面積（正方形的面積受限于長(zhǎng)和寬）
                      int t = Math.min(width, height);
                      ans = Math.max(ans, t * t);
                  }
              }
          }
          return ans;
      }
  }
  

  復(fù)雜度分析：

  • 時(shí)間復(fù)雜度：$O(n^2?m)$
  • 空間復(fù)雜度：$O(n?m)$

  其中 $n$ 為數(shù)組的行，$m$為數(shù)組的列

• 解法三：動(dòng)態(tài)規(guī)劃

• 解法四：?jiǎn)握{(diào)棧

  其實(shí)本題也是參考我前面寫(xiě)的那一題，這里再重新講解一下本題的思路（現(xiàn)在思路是有，但是代碼還有有一點(diǎn)寫(xiě)不出┭┮﹏┭┮）

  1. 構(gòu)建sum數(shù)組，sum數(shù)組就是縱向求和

     

     

     2. 一層一層的遍歷數(shù)組，把當(dāng)前層看著一個(gè)地平線

        比如第一層：

        

        我們?cè)诒闅v第一層的同時(shí)將柱子不斷加入棧中，保證棧是嚴(yán)格單調(diào)遞增的，因?yàn)橹挥斜３謼Ｖ兄邮菃握{(diào)遞增，我們才能夠確定左邊界（左邊矮，右邊高，自然左側(cè)柱子就是左邊界）

        

        

        不斷迭代，最終我們就可以得到最大正方形的面積

  import java.util.ArrayDeque;
  import java.util.Deque;
  
  /**
   * @author ghp
   * @title
   * @description
   */
  class Solution {
      public int maximalSquare(char[][] matrix) {
          int row = matrix.length;
          int col = matrix[0].length;
          // 構(gòu)建sum數(shù)組
          int[][] sum = new int[row + 1][col + 1];
          for (int i = 1; i <= row; i++) {
              for (int j = 1; j <= col; j++) {
                  sum[i][j] = matrix[i - 1][j - 1] == '0' ? 0 : sum[i - 1][j] + 1;
              }
          }
          // 遍歷每一層的柱子，更新max
          int ans = Integer.MIN_VALUE;
          for (int i = 1; i <= row; i++) {
              // 更新正方形的最大面積
              ans = Math.max(ans, largestSquareArea(sum[i]));
          }
          return ans;
      }
  
      private int largestSquareArea(int[] heights) {
          // 創(chuàng)建一個(gè)臨時(shí)數(shù)組，前0用于計(jì)算第一個(gè)柱子的面積，后一個(gè)0用于強(qiáng)制出棧（這一步超級(jí)重要）
          int[] tempArr = new int[heights.length + 2];
          for (int i = 1; i < heights.length + 1; i++) {
              tempArr[i] = heights[i - 1];
          }
          // 遞增棧（棧中存儲(chǔ)柱子的索引號(hào)，棧中的柱子的高度嚴(yán)格遞增）
          Deque<Integer> stack = new ArrayDeque<>();
          int ans = 0;
          for (int i = 0; i < tempArr.length; i++) {
              while (!stack.isEmpty() && tempArr[i] < tempArr[stack.peek()]) {
                  // 當(dāng)前柱子的右邊界已確定，可以計(jì)算已彈出柱子的面積
                  int height = tempArr[stack.poll()];
                  int width =  i - stack.peek() - 1;
                  int side = Math.min(height, width);
                  ans = Math.max(ans, side * side);
              }
              stack.push(i);
          }
          return ans;
      }
  }
  

  代碼優(yōu)化：

  這段代碼是我叫ChartGPT對(duì)上面代碼進(jìn)行的一個(gè)優(yōu)化，我也是試一試，沒(méi)想到他還真給我優(yōu)化了，這人工智能是真的牛，可能我沒(méi)有想到這樣子寫(xiě)，但是這個(gè)代碼還是能夠看的懂的??，優(yōu)化前我們通過(guò)自上而下遍歷數(shù)組構(gòu)建sum數(shù)組，但是發(fā)現(xiàn)矩形的最大面積的更新只跟當(dāng)前層有關(guān)，與下一層無(wú)關(guān)，所以我們可以在構(gòu)建sum數(shù)組的同時(shí)利用單調(diào)棧去更新當(dāng)前最大正方形的面積。這里優(yōu)化思路和前面的 往下擴(kuò)展==>往上擴(kuò)展 是一樣的，都是在構(gòu)建sum數(shù)組的時(shí)候更新最大正方形的面積，我相信只要看懂優(yōu)化前的代碼，優(yōu)化后的代碼也是很容易能夠看懂的，至于能否寫(xiě)出這么優(yōu)雅的代碼，就需要不但的積累和練習(xí)了，優(yōu)雅不是一蹴而就的，需要不斷積累，正如我刷題專欄上寫(xiě)的銘言：不積硅步無(wú)以至千里，不積小流無(wú)以至千里。天賦這東西不得不承認(rèn)他是存在的，但是這東西不是我所能決定的，后期的努力我所能決定的，我是堅(jiān)信能夠勤能補(bǔ)拙的，不渴望能夠媲美那些天賦型選手，只希望能戰(zhàn)勝和我差不多的選手，加油(? ?_?)?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-594721.html

  public int maximalSquare(char[][] matrix) {
      int rows = matrix.length;
      int cols = matrix[0].length;
      int[] heights = new int[cols + 1]; // 高度數(shù)組，最后一個(gè)元素為0
      
      int maxArea = 0;
      Deque<Integer> stack = new ArrayDeque<>(); // 單調(diào)棧，存放柱子的下標(biāo)
      
      for (int i = 0; i < rows; i++) {
          // 構(gòu)建柱狀圖，更新每一列的高度
          for (int j = 0; j < cols; j++) {
              if (matrix[i][j] == '1') {
                  heights[j]++;
              } else {
                  heights[j] = 0;
              }
          }
          
          stack.clear();
          
          // 計(jì)算每個(gè)柱子的面積
          for (int j = 0; j <= cols; j++) {
              while (!stack.isEmpty() && heights[j] < heights[stack.peek()]) {
                  // 當(dāng)前柱子的右邊界已確定，可以計(jì)算已彈出柱子的面積
                  int height = heights[stack.pop()];
                  int width = stack.isEmpty() ? j : (j - stack.peek() - 1);
                  int side = Math.min(height, width);
                  maxArea = Math.max(maxArea, side * side);
              }
              stack.push(j);
          }
      }
      
      return maxArea;
  }
  

到了這里，關(guān)于【LeetCode熱題100】打卡第39天：數(shù)組中第K個(gè)最大元素&最大正方形的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！