AOJ 0116 - Rectangular Searching

この２つの記事を参考に書きました．
ALGORITHM NOTE 長方形探索： 最大長方形の面積 Largest Rectangle
ALGORITHM NOTE ヒストグラム中の最大の長方形の面積
３ヶ月前は理解できなかったのでうれしいです．
ヒストグラムは単調増加の時はきれいに取り出せるのだと理解し，
長方形は１行に着目するとその１行を底辺とする長方形のもとができ，それをヒストグラムと考えとけばいいと知りました(説明が難しい)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
const int MAX_W = 500, MAX_H = 500;
int W, H;
std::string map[MAX_H];
int temp[MAX_H][MAX_W];

struct Rectangle{int height; int pos;};

int getLargestRect(int buffer[], int size){
	std::stack<Rectangle> s;
	buffer[size] = 0;
	int maxv = 0;
	for(int i=0;i<=size;i++){
		Rectangle rect;
		rect.height = buffer[i];
		rect.pos = i;
		if(s.empty()){
			s.push(rect);
		}
		else{
			if(s.top().height < rect.height){
				s.push(rect);
			}
			else if(s.top().height > rect.height){
				int target = i;
				while(!s.empty() && s.top().height >= rect.height){
					int area = (i - s.top().pos) * s.top().height;
					target = s.top().pos;
					maxv = std::max(maxv, area);
					s.pop();
				}
				rect.pos = target;
				s.push(rect);
			}
		}	
	}

	return maxv;
}

//初期処理をして求める
int getLargestRect(){
	memset(temp, 0, sizeof(temp));
	for(int j=0;j<W;j++){
		int seq = 0;
		for(int i=0;i<H;i++){
			if(map[i][j] == '*')
				seq = temp[i][j] = 0;
			else
				temp[i][j] = ++seq;
		}
	}

	int maxs = 0;
	for(int i=0;i<H;i++){
		maxs = std::max(maxs, getLargestRect(temp[i], W));
	}
	return maxs;
}

int main(){
	while(std::cin >> H >> W, W && H){
		for(int i=0;i<H;i++){
			std::cin >> map[i];
		}

		std::cout << getLargestRect() << std::endl;
	}
}