AOJ本の読書メモ
AOJ
次のAOJの問題へ
前のAOJの問題へ
DPL_3_C: ヒストグラムの中の最大長方形
C#のソース
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("8");
WillReturn.Add("2 1 3 5 3 4 2 1");
//12
}
else if (InputPattern == "Input2") {
WillReturn.Add("3");
WillReturn.Add("2 0 1");
//2
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
struct Rectangle
{
internal long Height;
internal long Pos;
}
static void Main()
{
List<string> InputList = GetInputList();
var HList = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToList();
var Stk = new Stack<Rectangle>();
long MaxArea = 0;
HList.Add(0); // 番兵をAdd
for (long I = 0; I <= HList.Count - 1; I++) {
Rectangle Rect;
Rect.Height = HList[(int)I];
Rect.Pos = I;
if (Stk.Count == 0) {
Stk.Push(Rect);
}
else if (Stk.Peek().Height < Rect.Height) {
Stk.Push(Rect);
}
else if (Stk.Peek().Height > Rect.Height) {
long Target = I;
while (Stk.Count > 0 && Stk.Peek().Height >= Rect.Height) {
Rectangle Pre = Stk.Pop();
long Area = Pre.Height * (I - Pre.Pos);
MaxArea = Math.Max(MaxArea, Area);
Target = Pre.Pos;
}
Rect.Pos = Target;
Stk.Push(Rect);
}
}
Console.WriteLine(MaxArea);
}
}
解説
ヒストグラムの高さを順次見ながら、
下記の3通りで処理を分岐させてます。
場合1
スタックが空の場合
場合2
スタックのトップにある長方形の高さが、カレントの長方形より低い場合
場合3
スタックのトップにある長方形の高さが、カレントの長方形より高い場合