Day21 Leetcode Array系列---- Largest Rectangle in Histogram

本次題目 Largest Rectangle in Histogram by JS

現在有一堆排列整齊的木牌，每個高度都不一樣，寬度均為1，現在希望從這些木牌中找出可畫出的最大長方形

Input: [2,1,5,6,2,3]
Output: 10

思考路線 1

1. 先來寫個測試好了，乘出的結果會等於 output
2. 會用到長度，長度就取最左與最右的木牌的位置
3. 高度就取木牌中的最小高度，這樣才能為出長方形
4. 將兩側的木牌比高度，如果左邊比右邊矮，就去掉左邊的木牌往中間推進，反之也是，這樣應該可以走過全部的木牌
5. 需要計算每一次畫出的長方形面積，每一次都與上一次面積做比較，把大的值留下
6. 這題可以用迴圈，迴圈終止條件就當沒有任何木牌為止，因為會一直把比較矮的木牌去除，迴圈到最後會把全部木牌都去除

Coding Time

先建立 temp 來存每一次長方形的面積，這樣就可以做比較， end 是要用來取陣列最後一個值，用 ary.length-1

input= [2,1,5,6,2,3]
output= 10

function rectangle(ary){
  temp = 0
  end = ary.length-1
  
  return temp
}

function expect(a,b){
  console.log( a == b )
}

expect(rectangle(input),output)

用 while 迴圈跑過整個陣列，當陣列中沒有任何值就中止 while 迴圈，現在的長方形面積就用陣列長度與陣列中最小值來算，當 temp 比 current 小，就把 temp 變成 current

Math.min(...ary) ，這個是先將目前陣列展開，再取這些數字中的最小值

input= [2,1,5,6,2,3]
output= 10

function rectangle(ary){
  temp = 0
  end = ary.length-1
  while(ary.length!=0){
    current = ary.length * Math.min(...ary)
    if(temp < current){
      temp = current
    } 
  }
  console.log(temp)
  return temp
}

function expect(a,b){
  console.log( a == b )
}

expect(rectangle(input),output)

去除木牌的方法就最左邊木牌高度與最右邊木牌高度比高低，把矮的去掉，去掉一個木牌，陣列長度也會變短一個，去除陣列數字的方法是用 pop() 與 shift()， 前者是拿出陣列尾端的值，後者是取出陣列最前端的值，這兩者都會改變原始陣列的狀況

input= [2,1,5,6,2,3]
output= 10

function rectangle(ary){
  temp = 0
  end = ary.length-1
  while(ary.length!=0){
    current = ary.length * Math.min(...ary)
    if(temp < current){
      temp = current
    }
    if(ary[0]<ary[end]){
      ary.shift()
      end -= 1
    }else{
      ary.pop()
      end-=1
    }
  }
  console.log(temp)
  return temp
}

function expect(a,b){
  console.log( a == b )
}

expect(rectangle(input),output)

今天到此為止，有任何問題請在下方留言或透過email、GitHub聯絡我，感謝閱讀

Daily kitty