import Mathlib /-! # Largest Rectangle In Histogram Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram. ## Constraints - 1 <= heights.length <= 10^5 - 0 <= heights[i] <= 10^4 ## Provided examples - `heights = [2, 1, 5, 6, 2, 3]` → `10` - `heights = [2, 4]` → `4` - `heights = [1]` → `1` ## Synthesized negative examples - invalid input: `heights = []` ([structural] a predicate that admits 1 <= heights.length <= 10^5. empty where at least one bar is required) - invalid input: `heights = [-1]` ([structural] a predicate that admits 0 <= heights[i] <= 10^4. negative height where non-negative is required) - invalid input: `heights = [10001]` ([structural] a predicate that admits 0 <= heights[i] <= 10^4. one above the stated maximum) - `heights = [2, 1, 5, 6, 2, 3]` → `11` is wrong ([structural] no rectangle is required to realize the returned bound. no rectangle in this histogram has area 11) - `heights = [2, 4]` → `2` is wrong ([structural] maximality stated as achievability alone. 2 is area of the first bar but not the largest) - `heights = [1]` → `2` is wrong ([structural] width computed as right-left instead of right-left-1. the single bar is counted twice) -/ namespace PLargestRectangleInHistogram abbrev Input := List Int abbrev Output := Nat /-! ### Specification helpers -/ /-- `left` and `right` bound a non-empty block of bars under which a rectangle of the given `height` fits: `left ≤ right < heights.length` and `height` is no greater than every bar in the block. -/ def IsRectangleInHistogram (heights : List Int) (left right height : Nat) : Prop := left ≤ right ∧ right < heights.length ∧ ∀ i (hi : i < heights.length), left ≤ i → i ≤ right → (height : Int) ≤ heights[i] /-! ### Validity predicate (V) -/ /-- Valid input: between 1 and 10^5 bars, each of height between 0 and 10^4. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 100000 && input.all (fun h => 0 ≤ h && h ≤ 10000) /-! ### Ideal specification (P_spec) -/ /-- `result` is the largest area of any rectangle contained in the histogram `input`: some block and height attain it, and no block and height exceed it. -/ def largestRectangleArea_spec (input : Input) (result : Output) : Prop := IsGreatest {area | ∃ left right height : Nat, IsRectangleInHistogram input left right height ∧ area = (right - left + 1) * height} result /-! ### Decidable specification (P_check) -/ /-- Decidability of rectangle containment, obtained by unfolding the predicate so the bounded quantifier over bar indices resolves. -/ instance isRectangleInHistogramDecidable (heights : List Int) (left right height : Nat) : Decidable (IsRectangleInHistogram heights left right height) := inferInstanceAs (Decidable (left ≤ right ∧ right < heights.length ∧ ∀ i (hi : i < heights.length), left ≤ i → i ≤ right → (height : Int) ≤ heights[i])) /-- Boolean checker for `largestRectangleArea_spec`, with rectangle heights drawn from bars. -/ def largestRectangleArea_check (input : Input) (result : Output) : Bool := decide ((∃ left right bar : Fin input.length, IsRectangleInHistogram input left.val right.val (input.get bar).toNat ∧ result = (right.val - left.val + 1) * (input.get bar).toNat) ∧ ∀ left right bar : Fin input.length, IsRectangleInHistogram input left.val right.val (input.get bar).toNat → (right.val - left.val + 1) * (input.get bar).toNat ≤ result) /-! ### Restatement of the `IsGreatest` spec with explicit binders -/ theorem lrh_spec_unfold (input : List Int) (result : Nat) : largestRectangleArea_spec input result ↔ ((∃ left right height : Nat, IsRectangleInHistogram input left right height ∧ result = (right - left + 1) * height) ∧ (∀ y : Nat, (∃ left right height : Nat, IsRectangleInHistogram input left right height ∧ y = (right - left + 1) * height) → y ≤ result)) := Iff.rfl /-- Every area the checker enumerates is an area the specification admits. -/ theorem lrh_bar_mem (input : List Int) (a : Nat) (ha : ∃ l r b : Fin input.length, IsRectangleInHistogram input l.val r.val (input.get b).toNat ∧ a = (r.val - l.val + 1) * (input.get b).toNat) : ∃ left right height : Nat, IsRectangleInHistogram input left right height ∧ a = (right - left + 1) * height := by obtain ⟨l, r, b, hrect, heq⟩ := ha exact ⟨l.val, r.val, (input.get b).toNat, hrect, heq⟩ /-- Every area the specification admits is dominated by one the checker enumerates: replace the free height by the smallest bar of the same block. -/ theorem lrh_dominated (input : List Int) (left right height : Nat) (hrect : IsRectangleInHistogram input left right height) : ∃ l r b : Fin input.length, IsRectangleInHistogram input l.val r.val (input.get b).toNat ∧ (right - left + 1) * height ≤ (r.val - l.val + 1) * (input.get b).toNat := by classical obtain ⟨hlr, hrn, hall⟩ := hrect have hln : left < input.length := lt_of_le_of_lt hlr hrn have hmemL : (⟨left, hln⟩ : Fin input.length) ∈ (Finset.univ.filter (fun i : Fin input.length => left ≤ i.val ∧ i.val ≤ right)) := by simp [hlr] obtain ⟨m, hmS, hmin⟩ := Finset.exists_min_image (Finset.univ.filter (fun i : Fin input.length => left ≤ i.val ∧ i.val ≤ right)) (fun i => input.get i) ⟨_, hmemL⟩ have hmb : left ≤ m.val ∧ m.val ≤ right := by simpa using hmS have hmh : (height : Int) ≤ input.get m := hall m.val m.isLt hmb.1 hmb.2 have hnn : (0 : Int) ≤ input.get m := le_trans (Int.natCast_nonneg height) hmh have hheight : height ≤ (input.get m).toNat := (Int.le_toNat hnn).mpr hmh refine ⟨⟨left, hln⟩, ⟨right, hrn⟩, m, ⟨hlr, hrn, ?_⟩, ?_⟩ · intro i hi h1 h2 have hiS : (⟨i, hi⟩ : Fin input.length) ∈ (Finset.univ.filter (fun i : Fin input.length => left ≤ i.val ∧ i.val ≤ right)) := by simp [h1, h2] have hle : input.get m ≤ input.get (⟨i, hi⟩ : Fin input.length) := hmin _ hiS rw [Int.toNat_of_nonneg hnn] exact hle · exact Nat.mul_le_mul_left _ hheight /-- On valid input the checker accepts exactly the specified outputs. -/ theorem largestRectangleArea_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : largestRectangleArea_check input result ↔ largestRectangleArea_spec input result := by rw [lrh_spec_unfold] unfold largestRectangleArea_check rw [decide_eq_true_eq] constructor · rintro ⟨⟨l, r, b, hrect, heq⟩, hub⟩ refine ⟨lrh_bar_mem input result ⟨l, r, b, hrect, heq⟩, ?_⟩ rintro y ⟨left, right, height, hrect2, hy⟩ obtain ⟨l2, r2, b2, hrect3, hle⟩ := lrh_dominated input left right height hrect2 rw [hy] exact le_trans hle (hub l2 r2 b2 hrect3) · rintro ⟨⟨left, right, height, hrect2, hy⟩, hub⟩ obtain ⟨l2, r2, b2, hrect3, hle⟩ := lrh_dominated input left right height hrect2 have hge : (r2.val - l2.val + 1) * (input.get b2).toNat ≤ result := hub _ (lrh_bar_mem input _ ⟨l2, r2, b2, hrect3, rfl⟩) have h1 : result ≤ (r2.val - l2.val + 1) * (input.get b2).toNat := by rw [hy]; exact hle refine ⟨⟨l2, r2, b2, hrect3, le_antisymm h1 hge⟩, ?_⟩ intro l3 r3 b3 hrect4 exact hub _ (lrh_bar_mem input _ ⟨l3, r3, b3, hrect4, rfl⟩) /-! ### Implementation helpers -/ /-- Pops stack entries whose bar is taller than the trigger height (or every entry when the trigger is `none`, the end-of-sweep drain), updating `best` with the rectangle whose minimum bar is each popped index. -/ def popAndUpdate (heights : List Int) (right : Nat) (trigger : Option Int) (stack : List Nat) (best : Nat) : Nat × List Nat := match stack with | [] => (best, []) | top :: rest => let shouldPop := match trigger with | none => true | some h => decide (heights[top]! > h) if shouldPop then let left := match rest with | [] => 0 | next :: _ => next + 1 popAndUpdate heights right trigger rest (Nat.max best (heights[top]!.toNat * (right - left))) else (best, top :: rest) /-- Sweeps the unprocessed suffix `rest` of `heights` (whose head sits at index `i`), popping taller bars with `popAndUpdate` before pushing the current index, and drains the stack at the end. -/ def sweep (heights rest : List Int) (i : Nat) (stack : List Nat) (best : Nat) : Nat := match rest with | [] => (popAndUpdate heights heights.length none stack best).1 | hcur :: tail => let (best', stack') := popAndUpdate heights i (some hcur) stack best sweep heights tail (i + 1) (i :: stack') best' /-! ### Main algorithm (impl) -/ /-- Largest rectangle area by a single sweep with a monotone stack of bar indices: each index is pushed once and popped at most once, O(n) total. -/ def largestRectangleAreaImpl (input : Input) : Output := sweep input input 0 [] 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem largestRectangleAreaImpl_correct (input : Input) (h : isValidInput input) : largestRectangleArea_spec input (largestRectangleAreaImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [2, 1, 5, 6, 2, 3] #guard isValidInput [2, 4] #guard isValidInput [1] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [(-1)]) #guard !(isValidInput [10001]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard largestRectangleArea_check [2, 1, 5, 6, 2, 3] 10 #guard largestRectangleArea_check [2, 4] 4 #guard largestRectangleArea_check [1] 1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(largestRectangleArea_check [2, 1, 5, 6, 2, 3] 11) #guard !(largestRectangleArea_check [2, 4] 2) #guard !(largestRectangleArea_check [1] 2) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard largestRectangleAreaImpl [2, 1, 5, 6, 2, 3] == 10 #guard largestRectangleAreaImpl [2, 4] == 4 #guard largestRectangleAreaImpl [1] == 1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard largestRectangleArea_check [2, 1, 5, 6, 2, 3] (largestRectangleAreaImpl [2, 1, 5, 6, 2, 3]) #guard largestRectangleArea_check [2, 4] (largestRectangleAreaImpl [2, 4]) #guard largestRectangleArea_check [1] (largestRectangleAreaImpl [1]) end PLargestRectangleInHistogram