借鑒——單調(diào)棧總結(jié)/懦榧酰客網(wǎng)左神算法進(jìn)階班
基本問題
對(duì)于一個(gè)數(shù)組arr, 針對(duì)每個(gè)數(shù)允青，尋找它和它左 / 右邊第一個(gè)比它大 / 小的數(shù)的值，以及相距多少個(gè)數(shù)卵沉。
基本思路：
創(chuàng)建一個(gè)棧颠锉，將數(shù)組中的元素下標(biāo)傳進(jìn)去。
遍歷arr數(shù)組史汗，如果椖炯恚空，則入棧
如果棧不為空淹办，且當(dāng)前棧頂元素值大于當(dāng)前arr遍歷到的位置的值，則直接入棧恶复。
如果棧不為空怜森，且當(dāng)前棧頂元素值小于當(dāng)前arr遍歷到的位置的值，則棧頂元素出棧谤牡，棧頂元素的左邊第一個(gè)比它大以及右邊第一個(gè)比他大的元素就可以確定了
如果棧不為空副硅，且當(dāng)前棧定元素值等于當(dāng)前arr遍歷到的位置的值，將具有相同值得數(shù)組索引下標(biāo)壓入一個(gè)鏈表或者數(shù)組翅萤。
可以確定得是恐疲，只有當(dāng)元素出棧得時(shí)候，我們才可以獲取到當(dāng)前元素左邊以及右邊得信息套么。
這里分別提供找出某個(gè)位置的右邊第一個(gè)大的數(shù)和左邊第一個(gè)大的數(shù)的方法培己。
代碼：
// 問題一：給定一個(gè)數(shù)組，請(qǐng)你返回每個(gè)元素右邊第一個(gè)大于它的元素,如果不存在則返回-1
public static int[] getFirstRightMax(int[] arr) {
if(arr == null || arr.length == 0) return null;
// 創(chuàng)建一個(gè)棧結(jié)構(gòu)
Stack<Integer> stack = new Stack<Integer>();
int[] res = new int[arr.length];
int i = 0;
while(i < arr.length) {
if(stack.isEmpty() || arr[stack.peek()] >= arr[i]) {
stack.push(i);
i++;
}else{
res[stack.pop()] = arr[i];
}
}
// 遍歷走完之后胚泌，棧中可能還剩余數(shù)組
while(!stack.isEmpty()){
res[stack.pop()] = -1;
}
return res;
}
// 問題二：給定一個(gè)數(shù)組省咨，請(qǐng)你返回每個(gè)元素左邊第一個(gè)大于它的元素,如果不存在則返回-1
public static int[] getFirstLeftMax(int[] arr) {
if(arr == null || arr.length == 0) return null;
Stack<Integer> stack = new Stack<Integer>();
int[] res = new int[arr.length];
int i = 0;
while(i < arr.length) {
if(stack.isEmpty() || arr[stack.peek()] >= arr[i]) {
stack.push(i);
i++;
}else{
res[stack.pop()] = stack.isEmpty() ? -1 : arr[stack.peek()];
}
}
while(!stack.isEmpty()){
res[stack.pop()] = stack.isEmpty() ? -1 : arr[stack.peek()];
}
return res;
}
public static void main(String[] args) {
int[] arr = new int[]{1,5,3,6,4,8,9,10};
int[] res1 = getFirstLeftMax(arr);
int[] res2 = getFirstRightMax(arr);
System.out.println(Arrays.toString(res1));
System.out.println(Arrays.toString(res2));
}
衍生問題一
給定 n 個(gè)非負(fù)整數(shù)，用來表示柱狀圖中各個(gè)柱子的高度玷室。每個(gè)柱子彼此相鄰零蓉，且寬度為 1 。
求在該柱狀圖中穷缤，能夠勾勒出來的矩形的最大面積敌蜂。
柱狀圖中最大的矩形
基本思路：
- 使用一個(gè)單調(diào)棧存儲(chǔ)一個(gè)單調(diào)遞增的序列，如果遇到大于等于棧頂元素的數(shù)組津肛，則入棧章喉，否則出棧，那么這么做的原因是什么尼？
-
首先考慮出棧的過程囊陡，只有當(dāng)前元素小于棧頂元素或者當(dāng)前高度數(shù)組已經(jīng)遍歷完了才會(huì)出棧芳绩，那么出棧也就意味著最大面積maxArea的更新，這也滿足單調(diào)棧出棧更新的思想撞反。具體更新思想可能看圖更容易明白妥色。
1
2
3
代碼如下：
//LeeCode84 借用單調(diào)棧的思想求解柱狀圖中的最大矩形面積
public static int largestRectangleArea(int[] heights) {
// 首先進(jìn)行邊界條件判端
if(heights == null || heights.length == 0) return 0;
if(heights.length == 1) return heights[0];
// 創(chuàng)建一個(gè)單調(diào)棧
Stack<Integer> stack = new Stack<Integer>();
int index = 0;
int maxArea = 0;
while(index < heights.length){
if(stack.isEmpty()){
stack.push(index++);
}else{
if(heights[stack.peek()] <= heights[index]){
stack.push(index++);
}else{
// 取出當(dāng)前棧頂元素對(duì)應(yīng)的高度
int topHeight = heights[stack.pop()];
// 獲取左邊一個(gè)數(shù)據(jù)的索引，這個(gè)數(shù)據(jù)和當(dāng)前的index之間肯定可以構(gòu)成構(gòu)成高度為height的矩陣
int leftIndex = stack.isEmpty() ? -1 : stack.peek();
// 更新maxArea
maxArea = Math.max(maxArea,(index - leftIndex - 1) * topHeight);
}
}
}
// 循環(huán)遍歷結(jié)束時(shí)遏片，index == arr.length; 還需要將棧中剩余的數(shù)據(jù)全部考慮進(jìn)去
while (!stack.isEmpty()) {
int topHeight = heights[stack.pop()];
int leftIndex = stack.isEmpty() ? -1 : stack.peek();
maxArea = Math.max(maxArea,(index - leftIndex - 1) * topHeight);
}
return maxArea;
}
衍生問題二——求二維數(shù)組中的最大矩形面積
題目描述：
最大矩形面積
基本思路：
- 此題的基本思路就是就是建立在前一題的基礎(chǔ)上求解的嘹害。將二維數(shù)組中每一行看作直方圖的底，不斷更新直方圖中每個(gè)位置矩形的高度吮便，按照前一題的求解思路即可笔呀。
代碼如下：
// 給定二維數(shù)組，求二維數(shù)組中最大的矩形面積
// LeeCode85題
public class Code_04_MaxArea {
public int maximalRectangle(char[][] matrix) {
if(matrix == null || matrix.length == 0) return 0;
int row = matrix.length;
int col = matrix[0].length;
int[] heights = new int[col];
int maxArea = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
heights[j] = matrix[i][j] == '0' ? 0 : heights[j] + 1;
}
maxArea = Math.max(maxArea,getMaxArea(heights));
}
return maxArea;
}
/**
* 給定一個(gè)直方圖的數(shù)組髓需，求該直方圖中最大的矩形面積
* @param heights
* @return
*/
private int getMaxArea(int[] heights) {
// 這里不進(jìn)行邊界判斷了许师，交給主函數(shù)
// 創(chuàng)建單調(diào)棧
Stack<Integer> stack = new Stack<Integer>();
int index = 0;
int maxArea = 0;
while(index < heights.length){
while(!stack.isEmpty() && heights[stack.peek()] >= heights[index]){
int h = stack.pop();
int l = stack.isEmpty() ? -1 : stack.peek();
maxArea = Math.max(maxArea,(index - l - 1) * heights[h]);
}
stack.push(index++);
}
while(!stack.isEmpty()){
int h =stack.pop();
int l = stack.isEmpty() ? -1 : stack.peek();
maxArea = Math.max(maxArea,(index - l - 1) * heights[h]);
}
return maxArea;
}
}
衍生問題三 —— 構(gòu)造數(shù)組的MaxTree
定義二叉樹的節(jié)點(diǎn)如下：
public class Node{
public int value;
public Node left;
public Node right;
public Node(int value){
this.value = value;
}
}
一個(gè)數(shù)組的maxTree定義如下:
- 數(shù)組中必須沒有重復(fù)元素；
- maxTree是一顆二叉樹僚匆，數(shù)組中每一個(gè)值對(duì)應(yīng)一個(gè)二叉樹中的節(jié)點(diǎn)微渠。
- 包括maxTree在內(nèi)且在其中的每一顆子樹上，值最大的節(jié)點(diǎn)都是當(dāng)前樹的頭節(jié)點(diǎn)咧擂。
- 指定沒有重復(fù)元素的數(shù)組arr逞盆，寫出這個(gè)數(shù)組的maxTree生成函數(shù)，要求如果數(shù)組長度為N松申，則時(shí)間復(fù)雜度為O(N), 空間復(fù)雜度為O(N).
基本思路：
方法一： 將數(shù)組arr生成一個(gè)大頂堆云芦，然后構(gòu)造出一個(gè)完全二叉樹。
方法二： 單調(diào)棧的思想贸桶，這里著重描述單調(diào)棧在這種問題中的求解思路舅逸。
首先通過單調(diào)棧求出每個(gè)位置上左邊第一個(gè)比它大的元素，右邊第一個(gè)比他大的元素刨啸。
如果某個(gè)位置上左右比他大的元素都沒有堡赔，則此位置的元素的值作為maxTree的根節(jié)點(diǎn)。
如果某個(gè)位置上左右兩邊有一個(gè)為null设联， 那么當(dāng)前的元素作為此處參數(shù)信息非null的那個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)善已。
如果某個(gè)位置上左右兩邊的參數(shù)都存在，那么當(dāng)前的元素作為左右兩邊較大的那個(gè)值的子節(jié)點(diǎn)离例。
衍生題四——最大可見山峰對(duì)
問題描述：
指定一個(gè)數(shù)組arr换团；
數(shù)組的中元素的含義為一個(gè)環(huán)形山脈每座山的高度；
規(guī)定宫蛆，相鄰的兩座山脈之間可以彼此看見艘包；
如果兩座山脈不相鄰的猛，兩座山脈之間的所有山脈不大于這兩座山脈的最小值時(shí)，這兩座山脈可以互相看見想虎。
現(xiàn)在希望你可以求出可以彼此看見的山脈總對(duì)數(shù)卦尊。
思路分析：
- 首先找到數(shù)組中的最大元素壓入單調(diào)棧中。
- 創(chuàng)建一個(gè)單調(diào)遞減的棧結(jié)構(gòu)
- 如果待壓入元素不滿足單調(diào)性棧舌厨，則從棧中彈出元素岂却，更新結(jié)果集
- 直到單調(diào)棧中元素更新結(jié)束，返回最終的結(jié)果集res裙椭。
1
2
3
代碼如下：
/**
*
* 左神算法進(jìn)階班第三課————單調(diào)棧
* 難度——頂尖
* 問題描述：
* 指定一個(gè)數(shù)組arr躏哩；
* 數(shù)組的中元素的含義為一個(gè)環(huán)形山脈每座山的高度；
* 規(guī)定揉燃，相鄰的兩座山脈之間可以彼此看見扫尺；
* 如果兩座山脈不相鄰，兩座山脈之間的所有山脈不大于這兩座山脈的最小值時(shí)炊汤，這兩座山脈可以互相看見。
* 現(xiàn)在希望你可以求出可以彼此看見的山脈總對(duì)數(shù)抢腐。
*
*/
public class Code_03_CircleMountain {
static class Pair{
int value; // 存放當(dāng)前山峰的高度拨拓，就是數(shù)組中某個(gè)位置的值
int times = 1; // 當(dāng)前山峰已經(jīng)出現(xiàn)的次數(shù)，也就是數(shù)組中某個(gè)位置元素出現(xiàn)的次數(shù)氓栈，初始化為1
Pair(int value) {
this.value = value;
}
}
/**
* 主函數(shù)入口，獲取彼此可以相互看見的最大山峰對(duì)
* @param arr
* @return
*/
public static long communications(int[] arr) {
if(arr == null || arr.length == 0) {
return 0;
}
int size = arr.length;
//-----更新出數(shù)組中最大元素的索引-----
int maxIndex = 0;
for (int i = 1; i < arr.length; i++) {
maxIndex = arr[maxIndex] < arr[i] ? i : maxIndex;
}
int value = arr[maxIndex];
int index = nextIndex(size,maxIndex);
long res = 0L;
//-----創(chuàng)建單調(diào)棧的結(jié)構(gòu)-----
Stack<Pair> stack = new Stack<Pair>();
//----首先將數(shù)組中最大的元素扔進(jìn)棧中----
stack.push(new Pair(value));
while(index != maxIndex){
value = arr[index];
// 如果棧不為空婿着，且當(dāng)前遍歷到的元素大于棧頂?shù)脑刂凳谑荩敲创颂幰聄es，可以增加山峰對(duì)了
while(!stack.isEmpty() && stack.peek().value < value) {
int times = stack.pop().times;
res += getInternalSum(times) + (2 * times);
}
if(!stack.isEmpty() && stack.peek().value == value){
stack.peek().times++;
}else{
stack.push(new Pair(value));
}
index = nextIndex(size,index);
}
// 當(dāng)棧不為null時(shí)竟宋，繼續(xù)遍歷
while(!stack.isEmpty()){
int times = stack.pop().times;
res += getInternalSum(times);
if(!stack.isEmpty()){
// 首先加上一個(gè)times
res += times;
if(stack.size() > 1){
//如果棧中剩余并不是最大的值提完，那么再加一個(gè)times,左右都可以找到最大的山峰
res += times;
} else{
// 否則，如果最大的山峰只有一個(gè)丘侠，那么只需要加一次times即可
res += stack.peek().times > 1 ? times : 0;
}
}
}
return res;
}
/**
* 獲取環(huán)中當(dāng)前位置的下一元素的索引
* @param size
* @param maxIndex
* @return
*/
private static int nextIndex(int size, int maxIndex) {
return maxIndex == size - 1 ? 0 : maxIndex + 1;
}
/**
* 獲取連續(xù)times相等的山峰可以構(gòu)成有效山峰對(duì)的數(shù)量
* @param times
* @return
*/
private static long getInternalSum(int times) {
return times == 1L ? 0 : (long)times * (long)(times - 1) / 2L;
}
// 測試函數(shù)
public static void main(String[] args) {
int[] arr = {1,2,3,3,3,4,4,5,5,6};
System.out.println(communications(arr));
}
}
